contrib/llvm/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 "MetadataImpl.h"
  17 #include "SymbolTableListTraitsImpl.h"
  18 #include "llvm/ADT/STLExtras.h"
  19 #include "llvm/ADT/SetVector.h"
  20 #include "llvm/ADT/SmallSet.h"
  21 #include "llvm/ADT/StringMap.h"
  22 #include "llvm/IR/ConstantRange.h"
  23 #include "llvm/IR/DebugInfoMetadata.h"
  24 #include "llvm/IR/Instruction.h"
  25 #include "llvm/IR/LLVMContext.h"
  26 #include "llvm/IR/Module.h"
  27 #include "llvm/IR/ValueHandle.h"
  28
  29 using namespace llvm;
  30
  31 MetadataAsValue::MetadataAsValue(Type *Ty, Metadata *MD)
  32     : Value(Ty, MetadataAsValueVal), MD(MD) {
  33   track();
  34 }
  35
  36 MetadataAsValue::~MetadataAsValue() {
  37   getType()->getContext().pImpl->MetadataAsValues.erase(MD);
  38   untrack();
  39 }
  40
  41 /// Canonicalize metadata arguments to intrinsics.
  42 ///
  43 /// To support bitcode upgrades (and assembly semantic sugar) for \a
  44 /// MetadataAsValue, we need to canonicalize certain metadata.
  45 ///
  46 ///   - nullptr is replaced by an empty MDNode.
  47 ///   - An MDNode with a single null operand is replaced by an empty MDNode.
  48 ///   - An MDNode whose only operand is a \a ConstantAsMetadata gets skipped.
  49 ///
  50 /// This maintains readability of bitcode from when metadata was a type of
  51 /// value, and these bridges were unnecessary.
  52 static Metadata *canonicalizeMetadataForValue(LLVMContext &Context,
  53                                               Metadata *MD) {
  54   if (!MD)
  55     // !{}
  56     return MDNode::get(Context, None);
  57
  58   // Return early if this isn't a single-operand MDNode.
  59   auto *N = dyn_cast<MDNode>(MD);
  60   if (!N || N->getNumOperands() != 1)
  61     return MD;
  62
  63   if (!N->getOperand(0))
  64     // !{}
  65     return MDNode::get(Context, None);
  66
  67   if (auto *C = dyn_cast<ConstantAsMetadata>(N->getOperand(0)))
  68     // Look through the MDNode.
  69     return C;
  70
  71   return MD;
  72 }
  73
  74 MetadataAsValue *MetadataAsValue::get(LLVMContext &Context, Metadata *MD) {
  75   MD = canonicalizeMetadataForValue(Context, MD);
  76   auto *&Entry = Context.pImpl->MetadataAsValues[MD];
  77   if (!Entry)
  78     Entry = new MetadataAsValue(Type::getMetadataTy(Context), MD);
  79   return Entry;
  80 }
  81
  82 MetadataAsValue *MetadataAsValue::getIfExists(LLVMContext &Context,
  83                                               Metadata *MD) {
  84   MD = canonicalizeMetadataForValue(Context, MD);
  85   auto &Store = Context.pImpl->MetadataAsValues;
  86   return Store.lookup(MD);
  87 }
  88
  89 void MetadataAsValue::handleChangedMetadata(Metadata *MD) {
  90   LLVMContext &Context = getContext();
  91   MD = canonicalizeMetadataForValue(Context, MD);
  92   auto &Store = Context.pImpl->MetadataAsValues;
  93
  94   // Stop tracking the old metadata.
  95   Store.erase(this->MD);
  96   untrack();
  97   this->MD = nullptr;
  98
  99   // Start tracking MD, or RAUW if necessary.
 100   auto *&Entry = Store[MD];
 101   if (Entry) {
 102     replaceAllUsesWith(Entry);
 103     delete this;
 104     return;
 105   }
 106
 107   this->MD = MD;
 108   track();
 109   Entry = this;
 110 }
 111
 112 void MetadataAsValue::track() {
 113   if (MD)
 114     MetadataTracking::track(&MD, *MD, *this);
 115 }
 116
 117 void MetadataAsValue::untrack() {
 118   if (MD)
 119     MetadataTracking::untrack(MD);
 120 }
 121
 122 bool MetadataTracking::track(void *Ref, Metadata &MD, OwnerTy Owner) {
 123   assert(Ref && "Expected live reference");
 124   assert((Owner || *static_cast<Metadata **>(Ref) == &MD) &&
 125          "Reference without owner must be direct");
 126   if (auto *R = ReplaceableMetadataImpl::getOrCreate(MD)) {
 127     R->addRef(Ref, Owner);
 128     return true;
 129   }
 130   if (auto *PH = dyn_cast<DistinctMDOperandPlaceholder>(&MD)) {
 131     assert(!PH->Use && "Placeholders can only be used once");
 132     assert(!Owner && "Unexpected callback to owner");
 133     PH->Use = static_cast<Metadata **>(Ref);
 134     return true;
 135   }
 136   return false;
 137 }
 138
 139 void MetadataTracking::untrack(void *Ref, Metadata &MD) {
 140   assert(Ref && "Expected live reference");
 141   if (auto *R = ReplaceableMetadataImpl::getIfExists(MD))
 142     R->dropRef(Ref);
 143   else if (auto *PH = dyn_cast<DistinctMDOperandPlaceholder>(&MD))
 144     PH->Use = nullptr;
 145 }
 146
 147 bool MetadataTracking::retrack(void *Ref, Metadata &MD, void *New) {
 148   assert(Ref && "Expected live reference");
 149   assert(New && "Expected live reference");
 150   assert(Ref != New && "Expected change");
 151   if (auto *R = ReplaceableMetadataImpl::getIfExists(MD)) {
 152     R->moveRef(Ref, New, MD);
 153     return true;
 154   }
 155   assert(!isa<DistinctMDOperandPlaceholder>(MD) &&
 156          "Unexpected move of an MDOperand");
 157   assert(!isReplaceable(MD) &&
 158          "Expected un-replaceable metadata, since we didn't move a reference");
 159   return false;
 160 }
 161
 162 bool MetadataTracking::isReplaceable(const Metadata &MD) {
 163   return ReplaceableMetadataImpl::isReplaceable(MD);
 164 }
 165
 166 void ReplaceableMetadataImpl::addRef(void *Ref, OwnerTy Owner) {
 167   bool WasInserted =
 168       UseMap.insert(std::make_pair(Ref, std::make_pair(Owner, NextIndex)))
 169           .second;
 170   (void)WasInserted;
 171   assert(WasInserted && "Expected to add a reference");
 172
 173   ++NextIndex;
 174   assert(NextIndex != 0 && "Unexpected overflow");
 175 }
 176
 177 void ReplaceableMetadataImpl::dropRef(void *Ref) {
 178   bool WasErased = UseMap.erase(Ref);
 179   (void)WasErased;
 180   assert(WasErased && "Expected to drop a reference");
 181 }
 182
 183 void ReplaceableMetadataImpl::moveRef(void *Ref, void *New,
 184                                       const Metadata &MD) {
 185   auto I = UseMap.find(Ref);
 186   assert(I != UseMap.end() && "Expected to move a reference");
 187   auto OwnerAndIndex = I->second;
 188   UseMap.erase(I);
 189   bool WasInserted = UseMap.insert(std::make_pair(New, OwnerAndIndex)).second;
 190   (void)WasInserted;
 191   assert(WasInserted && "Expected to add a reference");
 192
 193   // Check that the references are direct if there's no owner.
 194   (void)MD;
 195   assert((OwnerAndIndex.first || *static_cast<Metadata **>(Ref) == &MD) &&
 196          "Reference without owner must be direct");
 197   assert((OwnerAndIndex.first || *static_cast<Metadata **>(New) == &MD) &&
 198          "Reference without owner must be direct");
 199 }
 200
 201 void ReplaceableMetadataImpl::replaceAllUsesWith(Metadata *MD) {
 202   if (UseMap.empty())
 203     return;
 204
 205   // Copy out uses since UseMap will get touched below.
 206   typedef std::pair<void *, std::pair<OwnerTy, uint64_t>> UseTy;
 207   SmallVector<UseTy, 8> Uses(UseMap.begin(), UseMap.end());
 208   std::sort(Uses.begin(), Uses.end(), [](const UseTy &L, const UseTy &R) {
 209     return L.second.second < R.second.second;
 210   });
 211   for (const auto &Pair : Uses) {
 212     // Check that this Ref hasn't disappeared after RAUW (when updating a
 213     // previous Ref).
 214     if (!UseMap.count(Pair.first))
 215       continue;
 216
 217     OwnerTy Owner = Pair.second.first;
 218     if (!Owner) {
 219       // Update unowned tracking references directly.
 220       Metadata *&Ref = *static_cast<Metadata **>(Pair.first);
 221       Ref = MD;
 222       if (MD)
 223         MetadataTracking::track(Ref);
 224       UseMap.erase(Pair.first);
 225       continue;
 226     }
 227
 228     // Check for MetadataAsValue.
 229     if (Owner.is<MetadataAsValue *>()) {
 230       Owner.get<MetadataAsValue *>()->handleChangedMetadata(MD);
 231       continue;
 232     }
 233
 234     // There's a Metadata owner -- dispatch.
 235     Metadata *OwnerMD = Owner.get<Metadata *>();
 236     switch (OwnerMD->getMetadataID()) {
 237 #define HANDLE_METADATA_LEAF(CLASS)                                            \
 238   case Metadata::CLASS##Kind:                                                  \
 239     cast<CLASS>(OwnerMD)->handleChangedOperand(Pair.first, MD);                \
 240     continue;
 241 #include "llvm/IR/Metadata.def"
 242     default:
 243       llvm_unreachable("Invalid metadata subclass");
 244     }
 245   }
 246   assert(UseMap.empty() && "Expected all uses to be replaced");
 247 }
 248
 249 void ReplaceableMetadataImpl::resolveAllUses(bool ResolveUsers) {
 250   if (UseMap.empty())
 251     return;
 252
 253   if (!ResolveUsers) {
 254     UseMap.clear();
 255     return;
 256   }
 257
 258   // Copy out uses since UseMap could get touched below.
 259   typedef std::pair<void *, std::pair<OwnerTy, uint64_t>> UseTy;
 260   SmallVector<UseTy, 8> Uses(UseMap.begin(), UseMap.end());
 261   std::sort(Uses.begin(), Uses.end(), [](const UseTy &L, const UseTy &R) {
 262     return L.second.second < R.second.second;
 263   });
 264   UseMap.clear();
 265   for (const auto &Pair : Uses) {
 266     auto Owner = Pair.second.first;
 267     if (!Owner)
 268       continue;
 269     if (Owner.is<MetadataAsValue *>())
 270       continue;
 271
 272     // Resolve MDNodes that point at this.
 273     auto *OwnerMD = dyn_cast<MDNode>(Owner.get<Metadata *>());
 274     if (!OwnerMD)
 275       continue;
 276     if (OwnerMD->isResolved())
 277       continue;
 278     OwnerMD->decrementUnresolvedOperandCount();
 279   }
 280 }
 281
 282 ReplaceableMetadataImpl *ReplaceableMetadataImpl::getOrCreate(Metadata &MD) {
 283   if (auto *N = dyn_cast<MDNode>(&MD))
 284     return N->isResolved() ? nullptr : N->Context.getOrCreateReplaceableUses();
 285   return dyn_cast<ValueAsMetadata>(&MD);
 286 }
 287
 288 ReplaceableMetadataImpl *ReplaceableMetadataImpl::getIfExists(Metadata &MD) {
 289   if (auto *N = dyn_cast<MDNode>(&MD))
 290     return N->isResolved() ? nullptr : N->Context.getReplaceableUses();
 291   return dyn_cast<ValueAsMetadata>(&MD);
 292 }
 293
 294 bool ReplaceableMetadataImpl::isReplaceable(const Metadata &MD) {
 295   if (auto *N = dyn_cast<MDNode>(&MD))
 296     return !N->isResolved();
 297   return dyn_cast<ValueAsMetadata>(&MD);
 298 }
 299
 300 static Function *getLocalFunction(Value *V) {
 301   assert(V && "Expected value");
 302   if (auto *A = dyn_cast<Argument>(V))
 303     return A->getParent();
 304   if (BasicBlock *BB = cast<Instruction>(V)->getParent())
 305     return BB->getParent();
 306   return nullptr;
 307 }
 308
 309 ValueAsMetadata *ValueAsMetadata::get(Value *V) {
 310   assert(V && "Unexpected null Value");
 311
 312   auto &Context = V->getContext();
 313   auto *&Entry = Context.pImpl->ValuesAsMetadata[V];
 314   if (!Entry) {
 315     assert((isa<Constant>(V) || isa<Argument>(V) || isa<Instruction>(V)) &&
 316            "Expected constant or function-local value");
 317     assert(!V->IsUsedByMD && "Expected this to be the only metadata use");
 318     V->IsUsedByMD = true;
 319     if (auto *C = dyn_cast<Constant>(V))
 320       Entry = new ConstantAsMetadata(C);
 321     else
 322       Entry = new LocalAsMetadata(V);
 323   }
 324
 325   return Entry;
 326 }
 327
 328 ValueAsMetadata *ValueAsMetadata::getIfExists(Value *V) {
 329   assert(V && "Unexpected null Value");
 330   return V->getContext().pImpl->ValuesAsMetadata.lookup(V);
 331 }
 332
 333 void ValueAsMetadata::handleDeletion(Value *V) {
 334   assert(V && "Expected valid value");
 335
 336   auto &Store = V->getType()->getContext().pImpl->ValuesAsMetadata;
 337   auto I = Store.find(V);
 338   if (I == Store.end())
 339     return;
 340
 341   // Remove old entry from the map.
 342   ValueAsMetadata *MD = I->second;
 343   assert(MD && "Expected valid metadata");
 344   assert(MD->getValue() == V && "Expected valid mapping");
 345   Store.erase(I);
 346
 347   // Delete the metadata.
 348   MD->replaceAllUsesWith(nullptr);
 349   delete MD;
 350 }
 351
 352 void ValueAsMetadata::handleRAUW(Value *From, Value *To) {
 353   assert(From && "Expected valid value");
 354   assert(To && "Expected valid value");
 355   assert(From != To && "Expected changed value");
 356   assert(From->getType() == To->getType() && "Unexpected type change");
 357
 358   LLVMContext &Context = From->getType()->getContext();
 359   auto &Store = Context.pImpl->ValuesAsMetadata;
 360   auto I = Store.find(From);
 361   if (I == Store.end()) {
 362     assert(!From->IsUsedByMD && "Expected From not to be used by metadata");
 363     return;
 364   }
 365
 366   // Remove old entry from the map.
 367   assert(From->IsUsedByMD && "Expected From to be used by metadata");
 368   From->IsUsedByMD = false;
 369   ValueAsMetadata *MD = I->second;
 370   assert(MD && "Expected valid metadata");
 371   assert(MD->getValue() == From && "Expected valid mapping");
 372   Store.erase(I);
 373
 374   if (isa<LocalAsMetadata>(MD)) {
 375     if (auto *C = dyn_cast<Constant>(To)) {
 376       // Local became a constant.
 377       MD->replaceAllUsesWith(ConstantAsMetadata::get(C));
 378       delete MD;
 379       return;
 380     }
 381     if (getLocalFunction(From) && getLocalFunction(To) &&
 382         getLocalFunction(From) != getLocalFunction(To)) {
 383       // Function changed.
 384       MD->replaceAllUsesWith(nullptr);
 385       delete MD;
 386       return;
 387     }
 388   } else if (!isa<Constant>(To)) {
 389     // Changed to function-local value.
 390     MD->replaceAllUsesWith(nullptr);
 391     delete MD;
 392     return;
 393   }
 394
 395   auto *&Entry = Store[To];
 396   if (Entry) {
 397     // The target already exists.
 398     MD->replaceAllUsesWith(Entry);
 399     delete MD;
 400     return;
 401   }
 402
 403   // Update MD in place (and update the map entry).
 404   assert(!To->IsUsedByMD && "Expected this to be the only metadata use");
 405   To->IsUsedByMD = true;
 406   MD->V = To;
 407   Entry = MD;
 408 }
 409
 410 //===----------------------------------------------------------------------===//
 411 // MDString implementation.
 412 //
 413
 414 MDString *MDString::get(LLVMContext &Context, StringRef Str) {
 415   auto &Store = Context.pImpl->MDStringCache;
 416   auto I = Store.try_emplace(Str);
 417   auto &MapEntry = I.first->getValue();
 418   if (!I.second)
 419     return &MapEntry;
 420   MapEntry.Entry = &*I.first;
 421   return &MapEntry;
 422 }
 423
 424 StringRef MDString::getString() const {
 425   assert(Entry && "Expected to find string map entry");
 426   return Entry->first();
 427 }
 428
 429 //===----------------------------------------------------------------------===//
 430 // MDNode implementation.
 431 //
 432
 433 // Assert that the MDNode types will not be unaligned by the objects
 434 // prepended to them.
 435 #define HANDLE_MDNODE_LEAF(CLASS)                                              \
 436   static_assert(                                                               \
 437       alignof(uint64_t) >= alignof(CLASS),                                     \
 438       "Alignment is insufficient after objects prepended to " #CLASS);
 439 #include "llvm/IR/Metadata.def"
 440
 441 void *MDNode::operator new(size_t Size, unsigned NumOps) {
 442   size_t OpSize = NumOps * sizeof(MDOperand);
 443   // uint64_t is the most aligned type we need support (ensured by static_assert
 444   // above)
 445   OpSize = alignTo(OpSize, alignof(uint64_t));
 446   void *Ptr = reinterpret_cast<char *>(::operator new(OpSize + Size)) + OpSize;
 447   MDOperand *O = static_cast<MDOperand *>(Ptr);
 448   for (MDOperand *E = O - NumOps; O != E; --O)
 449     (void)new (O - 1) MDOperand;
 450   return Ptr;
 451 }
 452
 453 void MDNode::operator delete(void *Mem) {
 454   MDNode *N = static_cast<MDNode *>(Mem);
 455   size_t OpSize = N->NumOperands * sizeof(MDOperand);
 456   OpSize = alignTo(OpSize, alignof(uint64_t));
 457
 458   MDOperand *O = static_cast<MDOperand *>(Mem);
 459   for (MDOperand *E = O - N->NumOperands; O != E; --O)
 460     (O - 1)->~MDOperand();
 461   ::operator delete(reinterpret_cast<char *>(Mem) - OpSize);
 462 }
 463
 464 MDNode::MDNode(LLVMContext &Context, unsigned ID, StorageType Storage,
 465                ArrayRef<Metadata *> Ops1, ArrayRef<Metadata *> Ops2)
 466     : Metadata(ID, Storage), NumOperands(Ops1.size() + Ops2.size()),
 467       NumUnresolved(0), Context(Context) {
 468   unsigned Op = 0;
 469   for (Metadata *MD : Ops1)
 470     setOperand(Op++, MD);
 471   for (Metadata *MD : Ops2)
 472     setOperand(Op++, MD);
 473
 474   if (!isUniqued())
 475     return;
 476
 477   // Count the unresolved operands.  If there are any, RAUW support will be
 478   // added lazily on first reference.
 479   countUnresolvedOperands();
 480 }
 481
 482 TempMDNode MDNode::clone() const {
 483   switch (getMetadataID()) {
 484   default:
 485     llvm_unreachable("Invalid MDNode subclass");
 486 #define HANDLE_MDNODE_LEAF(CLASS)                                              \
 487   case CLASS##Kind:                                                            \
 488     return cast<CLASS>(this)->cloneImpl();
 489 #include "llvm/IR/Metadata.def"
 490   }
 491 }
 492
 493 static bool isOperandUnresolved(Metadata *Op) {
 494   if (auto *N = dyn_cast_or_null<MDNode>(Op))
 495     return !N->isResolved();
 496   return false;
 497 }
 498
 499 void MDNode::countUnresolvedOperands() {
 500   assert(NumUnresolved == 0 && "Expected unresolved ops to be uncounted");
 501   assert(isUniqued() && "Expected this to be uniqued");
 502   NumUnresolved = count_if(operands(), isOperandUnresolved);
 503 }
 504
 505 void MDNode::makeUniqued() {
 506   assert(isTemporary() && "Expected this to be temporary");
 507   assert(!isResolved() && "Expected this to be unresolved");
 508
 509   // Enable uniquing callbacks.
 510   for (auto &Op : mutable_operands())
 511     Op.reset(Op.get(), this);
 512
 513   // Make this 'uniqued'.
 514   Storage = Uniqued;
 515   countUnresolvedOperands();
 516   if (!NumUnresolved) {
 517     dropReplaceableUses();
 518     assert(isResolved() && "Expected this to be resolved");
 519   }
 520
 521   assert(isUniqued() && "Expected this to be uniqued");
 522 }
 523
 524 void MDNode::makeDistinct() {
 525   assert(isTemporary() && "Expected this to be temporary");
 526   assert(!isResolved() && "Expected this to be unresolved");
 527
 528   // Drop RAUW support and store as a distinct node.
 529   dropReplaceableUses();
 530   storeDistinctInContext();
 531
 532   assert(isDistinct() && "Expected this to be distinct");
 533   assert(isResolved() && "Expected this to be resolved");
 534 }
 535
 536 void MDNode::resolve() {
 537   assert(isUniqued() && "Expected this to be uniqued");
 538   assert(!isResolved() && "Expected this to be unresolved");
 539
 540   NumUnresolved = 0;
 541   dropReplaceableUses();
 542
 543   assert(isResolved() && "Expected this to be resolved");
 544 }
 545
 546 void MDNode::dropReplaceableUses() {
 547   assert(!NumUnresolved && "Unexpected unresolved operand");
 548
 549   // Drop any RAUW support.
 550   if (Context.hasReplaceableUses())
 551     Context.takeReplaceableUses()->resolveAllUses();
 552 }
 553
 554 void MDNode::resolveAfterOperandChange(Metadata *Old, Metadata *New) {
 555   assert(isUniqued() && "Expected this to be uniqued");
 556   assert(NumUnresolved != 0 && "Expected unresolved operands");
 557
 558   // Check if an operand was resolved.
 559   if (!isOperandUnresolved(Old)) {
 560     if (isOperandUnresolved(New))
 561       // An operand was un-resolved!
 562       ++NumUnresolved;
 563   } else if (!isOperandUnresolved(New))
 564     decrementUnresolvedOperandCount();
 565 }
 566
 567 void MDNode::decrementUnresolvedOperandCount() {
 568   assert(!isResolved() && "Expected this to be unresolved");
 569   if (isTemporary())
 570     return;
 571
 572   assert(isUniqued() && "Expected this to be uniqued");
 573   if (--NumUnresolved)
 574     return;
 575
 576   // Last unresolved operand has just been resolved.
 577   dropReplaceableUses();
 578   assert(isResolved() && "Expected this to become resolved");
 579 }
 580
 581 void MDNode::resolveCycles() {
 582   if (isResolved())
 583     return;
 584
 585   // Resolve this node immediately.
 586   resolve();
 587
 588   // Resolve all operands.
 589   for (const auto &Op : operands()) {
 590     auto *N = dyn_cast_or_null<MDNode>(Op);
 591     if (!N)
 592       continue;
 593
 594     assert(!N->isTemporary() &&
 595            "Expected all forward declarations to be resolved");
 596     if (!N->isResolved())
 597       N->resolveCycles();
 598   }
 599 }
 600
 601 static bool hasSelfReference(MDNode *N) {
 602   for (Metadata *MD : N->operands())
 603     if (MD == N)
 604       return true;
 605   return false;
 606 }
 607
 608 MDNode *MDNode::replaceWithPermanentImpl() {
 609   switch (getMetadataID()) {
 610   default:
 611     // If this type isn't uniquable, replace with a distinct node.
 612     return replaceWithDistinctImpl();
 613
 614 #define HANDLE_MDNODE_LEAF_UNIQUABLE(CLASS)                                    \
 615   case CLASS##Kind:                                                            \
 616     break;
 617 #include "llvm/IR/Metadata.def"
 618   }
 619
 620   // Even if this type is uniquable, self-references have to be distinct.
 621   if (hasSelfReference(this))
 622     return replaceWithDistinctImpl();
 623   return replaceWithUniquedImpl();
 624 }
 625
 626 MDNode *MDNode::replaceWithUniquedImpl() {
 627   // Try to uniquify in place.
 628   MDNode *UniquedNode = uniquify();
 629
 630   if (UniquedNode == this) {
 631     makeUniqued();
 632     return this;
 633   }
 634
 635   // Collision, so RAUW instead.
 636   replaceAllUsesWith(UniquedNode);
 637   deleteAsSubclass();
 638   return UniquedNode;
 639 }
 640
 641 MDNode *MDNode::replaceWithDistinctImpl() {
 642   makeDistinct();
 643   return this;
 644 }
 645
 646 void MDTuple::recalculateHash() {
 647   setHash(MDTupleInfo::KeyTy::calculateHash(this));
 648 }
 649
 650 void MDNode::dropAllReferences() {
 651   for (unsigned I = 0, E = NumOperands; I != E; ++I)
 652     setOperand(I, nullptr);
 653   if (Context.hasReplaceableUses()) {
 654     Context.getReplaceableUses()->resolveAllUses(/* ResolveUsers */ false);
 655     (void)Context.takeReplaceableUses();
 656   }
 657 }
 658
 659 void MDNode::handleChangedOperand(void *Ref, Metadata *New) {
 660   unsigned Op = static_cast<MDOperand *>(Ref) - op_begin();
 661   assert(Op < getNumOperands() && "Expected valid operand");
 662
 663   if (!isUniqued()) {
 664     // This node is not uniqued.  Just set the operand and be done with it.
 665     setOperand(Op, New);
 666     return;
 667   }
 668
 669   // This node is uniqued.
 670   eraseFromStore();
 671
 672   Metadata *Old = getOperand(Op);
 673   setOperand(Op, New);
 674
 675   // Drop uniquing for self-reference cycles and deleted constants.
 676   if (New == this || (!New && Old && isa<ConstantAsMetadata>(Old))) {
 677     if (!isResolved())
 678       resolve();
 679     storeDistinctInContext();
 680     return;
 681   }
 682
 683   // Re-unique the node.
 684   auto *Uniqued = uniquify();
 685   if (Uniqued == this) {
 686     if (!isResolved())
 687       resolveAfterOperandChange(Old, New);
 688     return;
 689   }
 690
 691   // Collision.
 692   if (!isResolved()) {
 693     // Still unresolved, so RAUW.
 694     //
 695     // First, clear out all operands to prevent any recursion (similar to
 696     // dropAllReferences(), but we still need the use-list).
 697     for (unsigned O = 0, E = getNumOperands(); O != E; ++O)
 698       setOperand(O, nullptr);
 699     if (Context.hasReplaceableUses())
 700       Context.getReplaceableUses()->replaceAllUsesWith(Uniqued);
 701     deleteAsSubclass();
 702     return;
 703   }
 704
 705   // Store in non-uniqued form if RAUW isn't possible.
 706   storeDistinctInContext();
 707 }
 708
 709 void MDNode::deleteAsSubclass() {
 710   switch (getMetadataID()) {
 711   default:
 712     llvm_unreachable("Invalid subclass of MDNode");
 713 #define HANDLE_MDNODE_LEAF(CLASS)                                              \
 714   case CLASS##Kind:                                                            \
 715     delete cast<CLASS>(this);                                                  \
 716     break;
 717 #include "llvm/IR/Metadata.def"
 718   }
 719 }
 720
 721 template <class T, class InfoT>
 722 static T *uniquifyImpl(T *N, DenseSet<T *, InfoT> &Store) {
 723   if (T *U = getUniqued(Store, N))
 724     return U;
 725
 726   Store.insert(N);
 727   return N;
 728 }
 729
 730 template <class NodeTy> struct MDNode::HasCachedHash {
 731   typedef char Yes[1];
 732   typedef char No[2];
 733   template <class U, U Val> struct SFINAE {};
 734
 735   template <class U>
 736   static Yes &check(SFINAE<void (U::*)(unsigned), &U::setHash> *);
 737   template <class U> static No &check(...);
 738
 739   static const bool value = sizeof(check<NodeTy>(nullptr)) == sizeof(Yes);
 740 };
 741
 742 MDNode *MDNode::uniquify() {
 743   assert(!hasSelfReference(this) && "Cannot uniquify a self-referencing node");
 744
 745   // Try to insert into uniquing store.
 746   switch (getMetadataID()) {
 747   default:
 748     llvm_unreachable("Invalid or non-uniquable subclass of MDNode");
 749 #define HANDLE_MDNODE_LEAF_UNIQUABLE(CLASS)                                    \
 750   case CLASS##Kind: {                                                          \
 751     CLASS *SubclassThis = cast<CLASS>(this);                                   \
 752     std::integral_constant<bool, HasCachedHash<CLASS>::value>                  \
 753         ShouldRecalculateHash;                                                 \
 754     dispatchRecalculateHash(SubclassThis, ShouldRecalculateHash);              \
 755     return uniquifyImpl(SubclassThis, getContext().pImpl->CLASS##s);           \
 756   }
 757 #include "llvm/IR/Metadata.def"
 758   }
 759 }
 760
 761 void MDNode::eraseFromStore() {
 762   switch (getMetadataID()) {
 763   default:
 764     llvm_unreachable("Invalid or non-uniquable subclass of MDNode");
 765 #define HANDLE_MDNODE_LEAF_UNIQUABLE(CLASS)                                    \
 766   case CLASS##Kind:                                                            \
 767     getContext().pImpl->CLASS##s.erase(cast<CLASS>(this));                     \
 768     break;
 769 #include "llvm/IR/Metadata.def"
 770   }
 771 }
 772
 773 MDTuple *MDTuple::getImpl(LLVMContext &Context, ArrayRef<Metadata *> MDs,
 774                           StorageType Storage, bool ShouldCreate) {
 775   unsigned Hash = 0;
 776   if (Storage == Uniqued) {
 777     MDTupleInfo::KeyTy Key(MDs);
 778     if (auto *N = getUniqued(Context.pImpl->MDTuples, Key))
 779       return N;
 780     if (!ShouldCreate)
 781       return nullptr;
 782     Hash = Key.getHash();
 783   } else {
 784     assert(ShouldCreate && "Expected non-uniqued nodes to always be created");
 785   }
 786
 787   return storeImpl(new (MDs.size()) MDTuple(Context, Storage, Hash, MDs),
 788                    Storage, Context.pImpl->MDTuples);
 789 }
 790
 791 void MDNode::deleteTemporary(MDNode *N) {
 792   assert(N->isTemporary() && "Expected temporary node");
 793   N->replaceAllUsesWith(nullptr);
 794   N->deleteAsSubclass();
 795 }
 796
 797 void MDNode::storeDistinctInContext() {
 798   assert(!Context.hasReplaceableUses() && "Unexpected replaceable uses");
 799   assert(!NumUnresolved && "Unexpected unresolved nodes");
 800   Storage = Distinct;
 801   assert(isResolved() && "Expected this to be resolved");
 802
 803   // Reset the hash.
 804   switch (getMetadataID()) {
 805   default:
 806     llvm_unreachable("Invalid subclass of MDNode");
 807 #define HANDLE_MDNODE_LEAF(CLASS)                                              \
 808   case CLASS##Kind: {                                                          \
 809     std::integral_constant<bool, HasCachedHash<CLASS>::value> ShouldResetHash; \
 810     dispatchResetHash(cast<CLASS>(this), ShouldResetHash);                     \
 811     break;                                                                     \
 812   }
 813 #include "llvm/IR/Metadata.def"
 814   }
 815
 816   getContext().pImpl->DistinctMDNodes.push_back(this);
 817 }
 818
 819 void MDNode::replaceOperandWith(unsigned I, Metadata *New) {
 820   if (getOperand(I) == New)
 821     return;
 822
 823   if (!isUniqued()) {
 824     setOperand(I, New);
 825     return;
 826   }
 827
 828   handleChangedOperand(mutable_begin() + I, New);
 829 }
 830
 831 void MDNode::setOperand(unsigned I, Metadata *New) {
 832   assert(I < NumOperands);
 833   mutable_begin()[I].reset(New, isUniqued() ? this : nullptr);
 834 }
 835
 836 /// Get a node or a self-reference that looks like it.
 837 ///
 838 /// Special handling for finding self-references, for use by \a
 839 /// MDNode::concatenate() and \a MDNode::intersect() to maintain behaviour from
 840 /// when self-referencing nodes were still uniqued.  If the first operand has
 841 /// the same operands as \c Ops, return the first operand instead.
 842 static MDNode *getOrSelfReference(LLVMContext &Context,
 843                                   ArrayRef<Metadata *> Ops) {
 844   if (!Ops.empty())
 845     if (MDNode *N = dyn_cast_or_null<MDNode>(Ops[0]))
 846       if (N->getNumOperands() == Ops.size() && N == N->getOperand(0)) {
 847         for (unsigned I = 1, E = Ops.size(); I != E; ++I)
 848           if (Ops[I] != N->getOperand(I))
 849             return MDNode::get(Context, Ops);
 850         return N;
 851       }
 852
 853   return MDNode::get(Context, Ops);
 854 }
 855
 856 MDNode *MDNode::concatenate(MDNode *A, MDNode *B) {
 857   if (!A)
 858     return B;
 859   if (!B)
 860     return A;
 861
 862   SmallSetVector<Metadata *, 4> MDs(A->op_begin(), A->op_end());
 863   MDs.insert(B->op_begin(), B->op_end());
 864
 865   // FIXME: This preserves long-standing behaviour, but is it really the right
 866   // behaviour?  Or was that an unintended side-effect of node uniquing?
 867   return getOrSelfReference(A->getContext(), MDs.getArrayRef());
 868 }
 869
 870 MDNode *MDNode::intersect(MDNode *A, MDNode *B) {
 871   if (!A || !B)
 872     return nullptr;
 873
 874   SmallSetVector<Metadata *, 4> MDs(A->op_begin(), A->op_end());
 875   SmallPtrSet<Metadata *, 4> BSet(B->op_begin(), B->op_end());
 876   MDs.remove_if([&](Metadata *MD) { return !is_contained(BSet, MD); });
 877
 878   // FIXME: This preserves long-standing behaviour, but is it really the right
 879   // behaviour?  Or was that an unintended side-effect of node uniquing?
 880   return getOrSelfReference(A->getContext(), MDs.getArrayRef());
 881 }
 882
 883 MDNode *MDNode::getMostGenericAliasScope(MDNode *A, MDNode *B) {
 884   if (!A || !B)
 885     return nullptr;
 886
 887   return concatenate(A, B);
 888 }
 889
 890 MDNode *MDNode::getMostGenericFPMath(MDNode *A, MDNode *B) {
 891   if (!A || !B)
 892     return nullptr;
 893
 894   APFloat AVal = mdconst::extract<ConstantFP>(A->getOperand(0))->getValueAPF();
 895   APFloat BVal = mdconst::extract<ConstantFP>(B->getOperand(0))->getValueAPF();
 896   if (AVal.compare(BVal) == APFloat::cmpLessThan)
 897     return A;
 898   return B;
 899 }
 900
 901 static bool isContiguous(const ConstantRange &A, const ConstantRange &B) {
 902   return A.getUpper() == B.getLower() || A.getLower() == B.getUpper();
 903 }
 904
 905 static bool canBeMerged(const ConstantRange &A, const ConstantRange &B) {
 906   return !A.intersectWith(B).isEmptySet() || isContiguous(A, B);
 907 }
 908
 909 static bool tryMergeRange(SmallVectorImpl<ConstantInt *> &EndPoints,
 910                           ConstantInt *Low, ConstantInt *High) {
 911   ConstantRange NewRange(Low->getValue(), High->getValue());
 912   unsigned Size = EndPoints.size();
 913   APInt LB = EndPoints[Size - 2]->getValue();
 914   APInt LE = EndPoints[Size - 1]->getValue();
 915   ConstantRange LastRange(LB, LE);
 916   if (canBeMerged(NewRange, LastRange)) {
 917     ConstantRange Union = LastRange.unionWith(NewRange);
 918     Type *Ty = High->getType();
 919     EndPoints[Size - 2] =
 920         cast<ConstantInt>(ConstantInt::get(Ty, Union.getLower()));
 921     EndPoints[Size - 1] =
 922         cast<ConstantInt>(ConstantInt::get(Ty, Union.getUpper()));
 923     return true;
 924   }
 925   return false;
 926 }
 927
 928 static void addRange(SmallVectorImpl<ConstantInt *> &EndPoints,
 929                      ConstantInt *Low, ConstantInt *High) {
 930   if (!EndPoints.empty())
 931     if (tryMergeRange(EndPoints, Low, High))
 932       return;
 933
 934   EndPoints.push_back(Low);
 935   EndPoints.push_back(High);
 936 }
 937
 938 MDNode *MDNode::getMostGenericRange(MDNode *A, MDNode *B) {
 939   // Given two ranges, we want to compute the union of the ranges. This
 940   // is slightly complitade by having to combine the intervals and merge
 941   // the ones that overlap.
 942
 943   if (!A || !B)
 944     return nullptr;
 945
 946   if (A == B)
 947     return A;
 948
 949   // First, walk both lists in older of the lower boundary of each interval.
 950   // At each step, try to merge the new interval to the last one we adedd.
 951   SmallVector<ConstantInt *, 4> EndPoints;
 952   int AI = 0;
 953   int BI = 0;
 954   int AN = A->getNumOperands() / 2;
 955   int BN = B->getNumOperands() / 2;
 956   while (AI < AN && BI < BN) {
 957     ConstantInt *ALow = mdconst::extract<ConstantInt>(A->getOperand(2 * AI));
 958     ConstantInt *BLow = mdconst::extract<ConstantInt>(B->getOperand(2 * BI));
 959
 960     if (ALow->getValue().slt(BLow->getValue())) {
 961       addRange(EndPoints, ALow,
 962                mdconst::extract<ConstantInt>(A->getOperand(2 * AI + 1)));
 963       ++AI;
 964     } else {
 965       addRange(EndPoints, BLow,
 966                mdconst::extract<ConstantInt>(B->getOperand(2 * BI + 1)));
 967       ++BI;
 968     }
 969   }
 970   while (AI < AN) {
 971     addRange(EndPoints, mdconst::extract<ConstantInt>(A->getOperand(2 * AI)),
 972              mdconst::extract<ConstantInt>(A->getOperand(2 * AI + 1)));
 973     ++AI;
 974   }
 975   while (BI < BN) {
 976     addRange(EndPoints, mdconst::extract<ConstantInt>(B->getOperand(2 * BI)),
 977              mdconst::extract<ConstantInt>(B->getOperand(2 * BI + 1)));
 978     ++BI;
 979   }
 980
 981   // If we have more than 2 ranges (4 endpoints) we have to try to merge
 982   // the last and first ones.
 983   unsigned Size = EndPoints.size();
 984   if (Size > 4) {
 985     ConstantInt *FB = EndPoints[0];
 986     ConstantInt *FE = EndPoints[1];
 987     if (tryMergeRange(EndPoints, FB, FE)) {
 988       for (unsigned i = 0; i < Size - 2; ++i) {
 989         EndPoints[i] = EndPoints[i + 2];
 990       }
 991       EndPoints.resize(Size - 2);
 992     }
 993   }
 994
 995   // If in the end we have a single range, it is possible that it is now the
 996   // full range. Just drop the metadata in that case.
 997   if (EndPoints.size() == 2) {
 998     ConstantRange Range(EndPoints[0]->getValue(), EndPoints[1]->getValue());
 999     if (Range.isFullSet())
1000       return nullptr;
1001   }
1002
1003   SmallVector<Metadata *, 4> MDs;
1004   MDs.reserve(EndPoints.size());
1005   for (auto *I : EndPoints)
1006     MDs.push_back(ConstantAsMetadata::get(I));
1007   return MDNode::get(A->getContext(), MDs);
1008 }
1009
1010 MDNode *MDNode::getMostGenericAlignmentOrDereferenceable(MDNode *A, MDNode *B) {
1011   if (!A || !B)
1012     return nullptr;
1013
1014   ConstantInt *AVal = mdconst::extract<ConstantInt>(A->getOperand(0));
1015   ConstantInt *BVal = mdconst::extract<ConstantInt>(B->getOperand(0));
1016   if (AVal->getZExtValue() < BVal->getZExtValue())
1017     return A;
1018   return B;
1019 }
1020
1021 //===----------------------------------------------------------------------===//
1022 // NamedMDNode implementation.
1023 //
1024
1025 static SmallVector<TrackingMDRef, 4> &getNMDOps(void *Operands) {
1026   return *(SmallVector<TrackingMDRef, 4> *)Operands;
1027 }
1028
1029 NamedMDNode::NamedMDNode(const Twine &N)
1030     : Name(N.str()), Parent(nullptr),
1031       Operands(new SmallVector<TrackingMDRef, 4>()) {}
1032
1033 NamedMDNode::~NamedMDNode() {
1034   dropAllReferences();
1035   delete &getNMDOps(Operands);
1036 }
1037
1038 unsigned NamedMDNode::getNumOperands() const {
1039   return (unsigned)getNMDOps(Operands).size();
1040 }
1041
1042 MDNode *NamedMDNode::getOperand(unsigned i) const {
1043   assert(i < getNumOperands() && "Invalid Operand number!");
1044   auto *N = getNMDOps(Operands)[i].get();
1045   return cast_or_null<MDNode>(N);
1046 }
1047
1048 void NamedMDNode::addOperand(MDNode *M) { getNMDOps(Operands).emplace_back(M); }
1049
1050 void NamedMDNode::setOperand(unsigned I, MDNode *New) {
1051   assert(I < getNumOperands() && "Invalid operand number");
1052   getNMDOps(Operands)[I].reset(New);
1053 }
1054
1055 void NamedMDNode::eraseFromParent() { getParent()->eraseNamedMetadata(this); }
1056
1057 void NamedMDNode::clearOperands() { getNMDOps(Operands).clear(); }
1058
1059 StringRef NamedMDNode::getName() const { return StringRef(Name); }
1060
1061 //===----------------------------------------------------------------------===//
1062 // Instruction Metadata method implementations.
1063 //
1064 void MDAttachmentMap::set(unsigned ID, MDNode &MD) {
1065   for (auto &I : Attachments)
1066     if (I.first == ID) {
1067       I.second.reset(&MD);
1068       return;
1069     }
1070   Attachments.emplace_back(std::piecewise_construct, std::make_tuple(ID),
1071                            std::make_tuple(&MD));
1072 }
1073
1074 void MDAttachmentMap::erase(unsigned ID) {
1075   if (empty())
1076     return;
1077
1078   // Common case is one/last value.
1079   if (Attachments.back().first == ID) {
1080     Attachments.pop_back();
1081     return;
1082   }
1083
1084   for (auto I = Attachments.begin(), E = std::prev(Attachments.end()); I != E;
1085        ++I)
1086     if (I->first == ID) {
1087       *I = std::move(Attachments.back());
1088       Attachments.pop_back();
1089       return;
1090     }
1091 }
1092
1093 MDNode *MDAttachmentMap::lookup(unsigned ID) const {
1094   for (const auto &I : Attachments)
1095     if (I.first == ID)
1096       return I.second;
1097   return nullptr;
1098 }
1099
1100 void MDAttachmentMap::getAll(
1101     SmallVectorImpl<std::pair<unsigned, MDNode *>> &Result) const {
1102   Result.append(Attachments.begin(), Attachments.end());
1103
1104   // Sort the resulting array so it is stable.
1105   if (Result.size() > 1)
1106     array_pod_sort(Result.begin(), Result.end());
1107 }
1108
1109 void MDGlobalAttachmentMap::insert(unsigned ID, MDNode &MD) {
1110   Attachments.push_back({ID, TrackingMDNodeRef(&MD)});
1111 }
1112
1113 void MDGlobalAttachmentMap::get(unsigned ID,
1114                                 SmallVectorImpl<MDNode *> &Result) {
1115   for (auto A : Attachments)
1116     if (A.MDKind == ID)
1117       Result.push_back(A.Node);
1118 }
1119
1120 void MDGlobalAttachmentMap::erase(unsigned ID) {
1121   auto Follower = Attachments.begin();
1122   for (auto Leader = Attachments.begin(), E = Attachments.end(); Leader != E;
1123        ++Leader) {
1124     if (Leader->MDKind != ID) {
1125       if (Follower != Leader)
1126         *Follower = std::move(*Leader);
1127       ++Follower;
1128     }
1129   }
1130   Attachments.resize(Follower - Attachments.begin());
1131 }
1132
1133 void MDGlobalAttachmentMap::getAll(
1134     SmallVectorImpl<std::pair<unsigned, MDNode *>> &Result) const {
1135   for (auto &A : Attachments)
1136     Result.emplace_back(A.MDKind, A.Node);
1137
1138   // Sort the resulting array so it is stable with respect to metadata IDs. We
1139   // need to preserve the original insertion order though.
1140   std::stable_sort(
1141       Result.begin(), Result.end(),
1142       [](const std::pair<unsigned, MDNode *> &A,
1143          const std::pair<unsigned, MDNode *> &B) { return A.first < B.first; });
1144 }
1145
1146 void Instruction::setMetadata(StringRef Kind, MDNode *Node) {
1147   if (!Node && !hasMetadata())
1148     return;
1149   setMetadata(getContext().getMDKindID(Kind), Node);
1150 }
1151
1152 MDNode *Instruction::getMetadataImpl(StringRef Kind) const {
1153   return getMetadataImpl(getContext().getMDKindID(Kind));
1154 }
1155
1156 void Instruction::dropUnknownNonDebugMetadata(ArrayRef<unsigned> KnownIDs) {
1157   if (!hasMetadataHashEntry())
1158     return; // Nothing to remove!
1159
1160   auto &InstructionMetadata = getContext().pImpl->InstructionMetadata;
1161
1162   SmallSet<unsigned, 4> KnownSet;
1163   KnownSet.insert(KnownIDs.begin(), KnownIDs.end());
1164   if (KnownSet.empty()) {
1165     // Just drop our entry at the store.
1166     InstructionMetadata.erase(this);
1167     setHasMetadataHashEntry(false);
1168     return;
1169   }
1170
1171   auto &Info = InstructionMetadata[this];
1172   Info.remove_if([&KnownSet](const std::pair<unsigned, TrackingMDNodeRef> &I) {
1173     return !KnownSet.count(I.first);
1174   });
1175
1176   if (Info.empty()) {
1177     // Drop our entry at the store.
1178     InstructionMetadata.erase(this);
1179     setHasMetadataHashEntry(false);
1180   }
1181 }
1182
1183 void Instruction::setMetadata(unsigned KindID, MDNode *Node) {
1184   if (!Node && !hasMetadata())
1185     return;
1186
1187   // Handle 'dbg' as a special case since it is not stored in the hash table.
1188   if (KindID == LLVMContext::MD_dbg) {
1189     DbgLoc = DebugLoc(Node);
1190     return;
1191   }
1192
1193   // Handle the case when we're adding/updating metadata on an instruction.
1194   if (Node) {
1195     auto &Info = getContext().pImpl->InstructionMetadata[this];
1196     assert(!Info.empty() == hasMetadataHashEntry() &&
1197            "HasMetadata bit is wonked");
1198     if (Info.empty())
1199       setHasMetadataHashEntry(true);
1200     Info.set(KindID, *Node);
1201     return;
1202   }
1203
1204   // Otherwise, we're removing metadata from an instruction.
1205   assert((hasMetadataHashEntry() ==
1206           (getContext().pImpl->InstructionMetadata.count(this) > 0)) &&
1207          "HasMetadata bit out of date!");
1208   if (!hasMetadataHashEntry())
1209     return; // Nothing to remove!
1210   auto &Info = getContext().pImpl->InstructionMetadata[this];
1211
1212   // Handle removal of an existing value.
1213   Info.erase(KindID);
1214
1215   if (!Info.empty())
1216     return;
1217
1218   getContext().pImpl->InstructionMetadata.erase(this);
1219   setHasMetadataHashEntry(false);
1220 }
1221
1222 void Instruction::setAAMetadata(const AAMDNodes &N) {
1223   setMetadata(LLVMContext::MD_tbaa, N.TBAA);
1224   setMetadata(LLVMContext::MD_alias_scope, N.Scope);
1225   setMetadata(LLVMContext::MD_noalias, N.NoAlias);
1226 }
1227
1228 MDNode *Instruction::getMetadataImpl(unsigned KindID) const {
1229   // Handle 'dbg' as a special case since it is not stored in the hash table.
1230   if (KindID == LLVMContext::MD_dbg)
1231     return DbgLoc.getAsMDNode();
1232
1233   if (!hasMetadataHashEntry())
1234     return nullptr;
1235   auto &Info = getContext().pImpl->InstructionMetadata[this];
1236   assert(!Info.empty() && "bit out of sync with hash table");
1237
1238   return Info.lookup(KindID);
1239 }
1240
1241 void Instruction::getAllMetadataImpl(
1242     SmallVectorImpl<std::pair<unsigned, MDNode *>> &Result) const {
1243   Result.clear();
1244
1245   // Handle 'dbg' as a special case since it is not stored in the hash table.
1246   if (DbgLoc) {
1247     Result.push_back(
1248         std::make_pair((unsigned)LLVMContext::MD_dbg, DbgLoc.getAsMDNode()));
1249     if (!hasMetadataHashEntry())
1250       return;
1251   }
1252
1253   assert(hasMetadataHashEntry() &&
1254          getContext().pImpl->InstructionMetadata.count(this) &&
1255          "Shouldn't have called this");
1256   const auto &Info = getContext().pImpl->InstructionMetadata.find(this)->second;
1257   assert(!Info.empty() && "Shouldn't have called this");
1258   Info.getAll(Result);
1259 }
1260
1261 void Instruction::getAllMetadataOtherThanDebugLocImpl(
1262     SmallVectorImpl<std::pair<unsigned, MDNode *>> &Result) const {
1263   Result.clear();
1264   assert(hasMetadataHashEntry() &&
1265          getContext().pImpl->InstructionMetadata.count(this) &&
1266          "Shouldn't have called this");
1267   const auto &Info = getContext().pImpl->InstructionMetadata.find(this)->second;
1268   assert(!Info.empty() && "Shouldn't have called this");
1269   Info.getAll(Result);
1270 }
1271
1272 bool Instruction::extractProfMetadata(uint64_t &TrueVal,
1273                                       uint64_t &FalseVal) const {
1274   assert(
1275       (getOpcode() == Instruction::Br || getOpcode() == Instruction::Select) &&
1276       "Looking for branch weights on something besides branch or select");
1277
1278   auto *ProfileData = getMetadata(LLVMContext::MD_prof);
1279   if (!ProfileData || ProfileData->getNumOperands() != 3)
1280     return false;
1281
1282   auto *ProfDataName = dyn_cast<MDString>(ProfileData->getOperand(0));
1283   if (!ProfDataName || !ProfDataName->getString().equals("branch_weights"))
1284     return false;
1285
1286   auto *CITrue = mdconst::dyn_extract<ConstantInt>(ProfileData->getOperand(1));
1287   auto *CIFalse = mdconst::dyn_extract<ConstantInt>(ProfileData->getOperand(2));
1288   if (!CITrue || !CIFalse)
1289     return false;
1290
1291   TrueVal = CITrue->getValue().getZExtValue();
1292   FalseVal = CIFalse->getValue().getZExtValue();
1293
1294   return true;
1295 }
1296
1297 bool Instruction::extractProfTotalWeight(uint64_t &TotalVal) const {
1298   assert((getOpcode() == Instruction::Br ||
1299           getOpcode() == Instruction::Select ||
1300           getOpcode() == Instruction::Call ||
1301           getOpcode() == Instruction::Invoke ||
1302           getOpcode() == Instruction::Switch) &&
1303          "Looking for branch weights on something besides branch");
1304
1305   TotalVal = 0;
1306   auto *ProfileData = getMetadata(LLVMContext::MD_prof);
1307   if (!ProfileData)
1308     return false;
1309
1310   auto *ProfDataName = dyn_cast<MDString>(ProfileData->getOperand(0));
1311   if (!ProfDataName || !ProfDataName->getString().equals("branch_weights"))
1312     return false;
1313
1314   TotalVal = 0;
1315   for (unsigned i = 1; i < ProfileData->getNumOperands(); i++) {
1316     auto *V = mdconst::dyn_extract<ConstantInt>(ProfileData->getOperand(i));
1317     if (!V)
1318       return false;
1319     TotalVal += V->getValue().getZExtValue();
1320   }
1321   return true;
1322 }
1323
1324 void Instruction::clearMetadataHashEntries() {
1325   assert(hasMetadataHashEntry() && "Caller should check");
1326   getContext().pImpl->InstructionMetadata.erase(this);
1327   setHasMetadataHashEntry(false);
1328 }
1329
1330 void GlobalObject::getMetadata(unsigned KindID,
1331                                SmallVectorImpl<MDNode *> &MDs) const {
1332   if (hasMetadata())
1333     getContext().pImpl->GlobalObjectMetadata[this].get(KindID, MDs);
1334 }
1335
1336 void GlobalObject::getMetadata(StringRef Kind,
1337                                SmallVectorImpl<MDNode *> &MDs) const {
1338   if (hasMetadata())
1339     getMetadata(getContext().getMDKindID(Kind), MDs);
1340 }
1341
1342 void GlobalObject::addMetadata(unsigned KindID, MDNode &MD) {
1343   if (!hasMetadata())
1344     setHasMetadataHashEntry(true);
1345
1346   getContext().pImpl->GlobalObjectMetadata[this].insert(KindID, MD);
1347 }
1348
1349 void GlobalObject::addMetadata(StringRef Kind, MDNode &MD) {
1350   addMetadata(getContext().getMDKindID(Kind), MD);
1351 }
1352
1353 void GlobalObject::eraseMetadata(unsigned KindID) {
1354   // Nothing to unset.
1355   if (!hasMetadata())
1356     return;
1357
1358   auto &Store = getContext().pImpl->GlobalObjectMetadata[this];
1359   Store.erase(KindID);
1360   if (Store.empty())
1361     clearMetadata();
1362 }
1363
1364 void GlobalObject::getAllMetadata(
1365     SmallVectorImpl<std::pair<unsigned, MDNode *>> &MDs) const {
1366   MDs.clear();
1367
1368   if (!hasMetadata())
1369     return;
1370
1371   getContext().pImpl->GlobalObjectMetadata[this].getAll(MDs);
1372 }
1373
1374 void GlobalObject::clearMetadata() {
1375   if (!hasMetadata())
1376     return;
1377   getContext().pImpl->GlobalObjectMetadata.erase(this);
1378   setHasMetadataHashEntry(false);
1379 }
1380
1381 void GlobalObject::setMetadata(unsigned KindID, MDNode *N) {
1382   eraseMetadata(KindID);
1383   if (N)
1384     addMetadata(KindID, *N);
1385 }
1386
1387 void GlobalObject::setMetadata(StringRef Kind, MDNode *N) {
1388   setMetadata(getContext().getMDKindID(Kind), N);
1389 }
1390
1391 MDNode *GlobalObject::getMetadata(unsigned KindID) const {
1392   SmallVector<MDNode *, 1> MDs;
1393   getMetadata(KindID, MDs);
1394   assert(MDs.size() <= 1 && "Expected at most one metadata attachment");
1395   if (MDs.empty())
1396     return nullptr;
1397   return MDs[0];
1398 }
1399
1400 MDNode *GlobalObject::getMetadata(StringRef Kind) const {
1401   return getMetadata(getContext().getMDKindID(Kind));
1402 }
1403
1404 void GlobalObject::copyMetadata(const GlobalObject *Other, unsigned Offset) {
1405   SmallVector<std::pair<unsigned, MDNode *>, 8> MDs;
1406   Other->getAllMetadata(MDs);
1407   for (auto &MD : MDs) {
1408     // We need to adjust the type metadata offset.
1409     if (Offset != 0 && MD.first == LLVMContext::MD_type) {
1410       auto *OffsetConst = cast<ConstantInt>(
1411           cast<ConstantAsMetadata>(MD.second->getOperand(0))->getValue());
1412       Metadata *TypeId = MD.second->getOperand(1);
1413       auto *NewOffsetMD = ConstantAsMetadata::get(ConstantInt::get(
1414           OffsetConst->getType(), OffsetConst->getValue() + Offset));
1415       addMetadata(LLVMContext::MD_type,
1416                   *MDNode::get(getContext(), {NewOffsetMD, TypeId}));
1417       continue;
1418     }
1419     // If an offset adjustment was specified we need to modify the DIExpression
1420     // to prepend the adjustment:
1421     // !DIExpression(DW_OP_plus, Offset, [original expr])
1422     auto *Attachment = MD.second;
1423     if (Offset != 0 && MD.first == LLVMContext::MD_dbg) {
1424       DIGlobalVariable *GV = dyn_cast<DIGlobalVariable>(Attachment);
1425       DIExpression *E = nullptr;
1426       if (!GV) {
1427         auto *GVE = cast<DIGlobalVariableExpression>(Attachment);
1428         GV = GVE->getVariable();
1429         E = GVE->getExpression();
1430       }
1431       ArrayRef<uint64_t> OrigElements;
1432       if (E)
1433         OrigElements = E->getElements();
1434       std::vector<uint64_t> Elements(OrigElements.size() + 2);
1435       Elements[0] = dwarf::DW_OP_plus;
1436       Elements[1] = Offset;
1437       std::copy(OrigElements.begin(), OrigElements.end(), Elements.begin() + 2);
1438       E = DIExpression::get(getContext(), Elements);
1439       Attachment = DIGlobalVariableExpression::get(getContext(), GV, E);
1440     }
1441     addMetadata(MD.first, *Attachment);
1442   }
1443 }
1444
1445 void GlobalObject::addTypeMetadata(unsigned Offset, Metadata *TypeID) {
1446   addMetadata(
1447       LLVMContext::MD_type,
1448       *MDTuple::get(getContext(),
1449                     {llvm::ConstantAsMetadata::get(llvm::ConstantInt::get(
1450                          Type::getInt64Ty(getContext()), Offset)),
1451                      TypeID}));
1452 }
1453
1454 void Function::setSubprogram(DISubprogram *SP) {
1455   setMetadata(LLVMContext::MD_dbg, SP);
1456 }
1457
1458 DISubprogram *Function::getSubprogram() const {
1459   return cast_or_null<DISubprogram>(getMetadata(LLVMContext::MD_dbg));
1460 }
1461
1462 void GlobalVariable::addDebugInfo(DIGlobalVariableExpression *GV) {
1463   addMetadata(LLVMContext::MD_dbg, *GV);
1464 }
1465
1466 void GlobalVariable::getDebugInfo(
1467     SmallVectorImpl<DIGlobalVariableExpression *> &GVs) const {
1468   SmallVector<MDNode *, 1> MDs;
1469   getMetadata(LLVMContext::MD_dbg, MDs);
1470   for (MDNode *MD : MDs)
1471     GVs.push_back(cast<DIGlobalVariableExpression>(MD));
1472 }