llvm/lib/IR/Metadata.cpp

   1 //===- Metadata.cpp - Implement Metadata classes --------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file implements the Metadata classes.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "llvm/IR/Metadata.h"
  14 #include "LLVMContextImpl.h"
  15 #include "MetadataImpl.h"
  16 #include "llvm/ADT/APFloat.h"
  17 #include "llvm/ADT/APInt.h"
  18 #include "llvm/ADT/ArrayRef.h"
  19 #include "llvm/ADT/DenseSet.h"
  20 #include "llvm/ADT/STLExtras.h"
  21 #include "llvm/ADT/SetVector.h"
  22 #include "llvm/ADT/SmallPtrSet.h"
  23 #include "llvm/ADT/SmallSet.h"
  24 #include "llvm/ADT/SmallVector.h"
  25 #include "llvm/ADT/StringMap.h"
  26 #include "llvm/ADT/StringRef.h"
  27 #include "llvm/ADT/Twine.h"
  28 #include "llvm/IR/Argument.h"
  29 #include "llvm/IR/BasicBlock.h"
  30 #include "llvm/IR/Constant.h"
  31 #include "llvm/IR/ConstantRange.h"
  32 #include "llvm/IR/Constants.h"
  33 #include "llvm/IR/DebugInfoMetadata.h"
  34 #include "llvm/IR/DebugLoc.h"
  35 #include "llvm/IR/Function.h"
  36 #include "llvm/IR/GlobalObject.h"
  37 #include "llvm/IR/GlobalVariable.h"
  38 #include "llvm/IR/Instruction.h"
  39 #include "llvm/IR/LLVMContext.h"
  40 #include "llvm/IR/MDBuilder.h"
  41 #include "llvm/IR/Module.h"
  42 #include "llvm/IR/ProfDataUtils.h"
  43 #include "llvm/IR/TrackingMDRef.h"
  44 #include "llvm/IR/Type.h"
  45 #include "llvm/IR/Value.h"
  46 #include "llvm/Support/Casting.h"
  47 #include "llvm/Support/ErrorHandling.h"
  48 #include "llvm/Support/MathExtras.h"
  49 #include <algorithm>
  50 #include <cassert>
  51 #include <cstddef>
  52 #include <cstdint>
  53 #include <type_traits>
  54 #include <utility>
  55 #include <vector>
  56
  57 using namespace llvm;
  58
  59 MetadataAsValue::MetadataAsValue(Type *Ty, Metadata *MD)
  60     : Value(Ty, MetadataAsValueVal), MD(MD) {
  61   track();
  62 }
  63
  64 MetadataAsValue::~MetadataAsValue() {
  65   getType()->getContext().pImpl->MetadataAsValues.erase(MD);
  66   untrack();
  67 }
  68
  69 /// Canonicalize metadata arguments to intrinsics.
  70 ///
  71 /// To support bitcode upgrades (and assembly semantic sugar) for \a
  72 /// MetadataAsValue, we need to canonicalize certain metadata.
  73 ///
  74 ///   - nullptr is replaced by an empty MDNode.
  75 ///   - An MDNode with a single null operand is replaced by an empty MDNode.
  76 ///   - An MDNode whose only operand is a \a ConstantAsMetadata gets skipped.
  77 ///
  78 /// This maintains readability of bitcode from when metadata was a type of
  79 /// value, and these bridges were unnecessary.
  80 static Metadata *canonicalizeMetadataForValue(LLVMContext &Context,
  81                                               Metadata *MD) {
  82   if (!MD)
  83     // !{}
  84     return MDNode::get(Context, std::nullopt);
  85
  86   // Return early if this isn't a single-operand MDNode.
  87   auto *N = dyn_cast<MDNode>(MD);
  88   if (!N || N->getNumOperands() != 1)
  89     return MD;
  90
  91   if (!N->getOperand(0))
  92     // !{}
  93     return MDNode::get(Context, std::nullopt);
  94
  95   if (auto *C = dyn_cast<ConstantAsMetadata>(N->getOperand(0)))
  96     // Look through the MDNode.
  97     return C;
  98
  99   return MD;
 100 }
 101
 102 MetadataAsValue *MetadataAsValue::get(LLVMContext &Context, Metadata *MD) {
 103   MD = canonicalizeMetadataForValue(Context, MD);
 104   auto *&Entry = Context.pImpl->MetadataAsValues[MD];
 105   if (!Entry)
 106     Entry = new MetadataAsValue(Type::getMetadataTy(Context), MD);
 107   return Entry;
 108 }
 109
 110 MetadataAsValue *MetadataAsValue::getIfExists(LLVMContext &Context,
 111                                               Metadata *MD) {
 112   MD = canonicalizeMetadataForValue(Context, MD);
 113   auto &Store = Context.pImpl->MetadataAsValues;
 114   return Store.lookup(MD);
 115 }
 116
 117 void MetadataAsValue::handleChangedMetadata(Metadata *MD) {
 118   LLVMContext &Context = getContext();
 119   MD = canonicalizeMetadataForValue(Context, MD);
 120   auto &Store = Context.pImpl->MetadataAsValues;
 121
 122   // Stop tracking the old metadata.
 123   Store.erase(this->MD);
 124   untrack();
 125   this->MD = nullptr;
 126
 127   // Start tracking MD, or RAUW if necessary.
 128   auto *&Entry = Store[MD];
 129   if (Entry) {
 130     replaceAllUsesWith(Entry);
 131     delete this;
 132     return;
 133   }
 134
 135   this->MD = MD;
 136   track();
 137   Entry = this;
 138 }
 139
 140 void MetadataAsValue::track() {
 141   if (MD)
 142     MetadataTracking::track(&MD, *MD, *this);
 143 }
 144
 145 void MetadataAsValue::untrack() {
 146   if (MD)
 147     MetadataTracking::untrack(MD);
 148 }
 149
 150 bool MetadataTracking::track(void *Ref, Metadata &MD, OwnerTy Owner) {
 151   assert(Ref && "Expected live reference");
 152   assert((Owner || *static_cast<Metadata **>(Ref) == &MD) &&
 153          "Reference without owner must be direct");
 154   if (auto *R = ReplaceableMetadataImpl::getOrCreate(MD)) {
 155     R->addRef(Ref, Owner);
 156     return true;
 157   }
 158   if (auto *PH = dyn_cast<DistinctMDOperandPlaceholder>(&MD)) {
 159     assert(!PH->Use && "Placeholders can only be used once");
 160     assert(!Owner && "Unexpected callback to owner");
 161     PH->Use = static_cast<Metadata **>(Ref);
 162     return true;
 163   }
 164   return false;
 165 }
 166
 167 void MetadataTracking::untrack(void *Ref, Metadata &MD) {
 168   assert(Ref && "Expected live reference");
 169   if (auto *R = ReplaceableMetadataImpl::getIfExists(MD))
 170     R->dropRef(Ref);
 171   else if (auto *PH = dyn_cast<DistinctMDOperandPlaceholder>(&MD))
 172     PH->Use = nullptr;
 173 }
 174
 175 bool MetadataTracking::retrack(void *Ref, Metadata &MD, void *New) {
 176   assert(Ref && "Expected live reference");
 177   assert(New && "Expected live reference");
 178   assert(Ref != New && "Expected change");
 179   if (auto *R = ReplaceableMetadataImpl::getIfExists(MD)) {
 180     R->moveRef(Ref, New, MD);
 181     return true;
 182   }
 183   assert(!isa<DistinctMDOperandPlaceholder>(MD) &&
 184          "Unexpected move of an MDOperand");
 185   assert(!isReplaceable(MD) &&
 186          "Expected un-replaceable metadata, since we didn't move a reference");
 187   return false;
 188 }
 189
 190 bool MetadataTracking::isReplaceable(const Metadata &MD) {
 191   return ReplaceableMetadataImpl::isReplaceable(MD);
 192 }
 193
 194 SmallVector<Metadata *> ReplaceableMetadataImpl::getAllArgListUsers() {
 195   SmallVector<std::pair<OwnerTy, uint64_t> *> MDUsersWithID;
 196   for (auto Pair : UseMap) {
 197     OwnerTy Owner = Pair.second.first;
 198     if (!isa<Metadata *>(Owner))
 199       continue;
 200     Metadata *OwnerMD = cast<Metadata *>(Owner);
 201     if (OwnerMD->getMetadataID() == Metadata::DIArgListKind)
 202       MDUsersWithID.push_back(&UseMap[Pair.first]);
 203   }
 204   llvm::sort(MDUsersWithID, [](auto UserA, auto UserB) {
 205     return UserA->second < UserB->second;
 206   });
 207   SmallVector<Metadata *> MDUsers;
 208   for (auto *UserWithID : MDUsersWithID)
 209     MDUsers.push_back(cast<Metadata *>(UserWithID->first));
 210   return MDUsers;
 211 }
 212
 213 void ReplaceableMetadataImpl::addRef(void *Ref, OwnerTy Owner) {
 214   bool WasInserted =
 215       UseMap.insert(std::make_pair(Ref, std::make_pair(Owner, NextIndex)))
 216           .second;
 217   (void)WasInserted;
 218   assert(WasInserted && "Expected to add a reference");
 219
 220   ++NextIndex;
 221   assert(NextIndex != 0 && "Unexpected overflow");
 222 }
 223
 224 void ReplaceableMetadataImpl::dropRef(void *Ref) {
 225   bool WasErased = UseMap.erase(Ref);
 226   (void)WasErased;
 227   assert(WasErased && "Expected to drop a reference");
 228 }
 229
 230 void ReplaceableMetadataImpl::moveRef(void *Ref, void *New,
 231                                       const Metadata &MD) {
 232   auto I = UseMap.find(Ref);
 233   assert(I != UseMap.end() && "Expected to move a reference");
 234   auto OwnerAndIndex = I->second;
 235   UseMap.erase(I);
 236   bool WasInserted = UseMap.insert(std::make_pair(New, OwnerAndIndex)).second;
 237   (void)WasInserted;
 238   assert(WasInserted && "Expected to add a reference");
 239
 240   // Check that the references are direct if there's no owner.
 241   (void)MD;
 242   assert((OwnerAndIndex.first || *static_cast<Metadata **>(Ref) == &MD) &&
 243          "Reference without owner must be direct");
 244   assert((OwnerAndIndex.first || *static_cast<Metadata **>(New) == &MD) &&
 245          "Reference without owner must be direct");
 246 }
 247
 248 void ReplaceableMetadataImpl::SalvageDebugInfo(const Constant &C) {
 249   if (!C.isUsedByMetadata()) {
 250     return;
 251   }
 252
 253   LLVMContext &Context = C.getType()->getContext();
 254   auto &Store = Context.pImpl->ValuesAsMetadata;
 255   auto I = Store.find(&C);
 256   ValueAsMetadata *MD = I->second;
 257   using UseTy =
 258       std::pair<void *, std::pair<MetadataTracking::OwnerTy, uint64_t>>;
 259   // Copy out uses and update value of Constant used by debug info metadata with undef below
 260   SmallVector<UseTy, 8> Uses(MD->UseMap.begin(), MD->UseMap.end());
 261
 262   for (const auto &Pair : Uses) {
 263     MetadataTracking::OwnerTy Owner = Pair.second.first;
 264     if (!Owner)
 265       continue;
 266     if (!isa<Metadata *>(Owner))
 267       continue;
 268     auto *OwnerMD = dyn_cast_if_present<MDNode>(cast<Metadata *>(Owner));
 269     if (!OwnerMD)
 270       continue;
 271     if (isa<DINode>(OwnerMD)) {
 272       OwnerMD->handleChangedOperand(
 273           Pair.first, ValueAsMetadata::get(UndefValue::get(C.getType())));
 274     }
 275   }
 276 }
 277
 278 void ReplaceableMetadataImpl::replaceAllUsesWith(Metadata *MD) {
 279   if (UseMap.empty())
 280     return;
 281
 282   // Copy out uses since UseMap will get touched below.
 283   using UseTy = std::pair<void *, std::pair<OwnerTy, uint64_t>>;
 284   SmallVector<UseTy, 8> Uses(UseMap.begin(), UseMap.end());
 285   llvm::sort(Uses, [](const UseTy &L, const UseTy &R) {
 286     return L.second.second < R.second.second;
 287   });
 288   for (const auto &Pair : Uses) {
 289     // Check that this Ref hasn't disappeared after RAUW (when updating a
 290     // previous Ref).
 291     if (!UseMap.count(Pair.first))
 292       continue;
 293
 294     OwnerTy Owner = Pair.second.first;
 295     if (!Owner) {
 296       // Update unowned tracking references directly.
 297       Metadata *&Ref = *static_cast<Metadata **>(Pair.first);
 298       Ref = MD;
 299       if (MD)
 300         MetadataTracking::track(Ref);
 301       UseMap.erase(Pair.first);
 302       continue;
 303     }
 304
 305     // Check for MetadataAsValue.
 306     if (isa<MetadataAsValue *>(Owner)) {
 307       cast<MetadataAsValue *>(Owner)->handleChangedMetadata(MD);
 308       continue;
 309     }
 310
 311     // There's a Metadata owner -- dispatch.
 312     Metadata *OwnerMD = cast<Metadata *>(Owner);
 313     switch (OwnerMD->getMetadataID()) {
 314 #define HANDLE_METADATA_LEAF(CLASS)                                            \
 315   case Metadata::CLASS##Kind:                                                  \
 316     cast<CLASS>(OwnerMD)->handleChangedOperand(Pair.first, MD);                \
 317     continue;
 318 #include "llvm/IR/Metadata.def"
 319     default:
 320       llvm_unreachable("Invalid metadata subclass");
 321     }
 322   }
 323   assert(UseMap.empty() && "Expected all uses to be replaced");
 324 }
 325
 326 void ReplaceableMetadataImpl::resolveAllUses(bool ResolveUsers) {
 327   if (UseMap.empty())
 328     return;
 329
 330   if (!ResolveUsers) {
 331     UseMap.clear();
 332     return;
 333   }
 334
 335   // Copy out uses since UseMap could get touched below.
 336   using UseTy = std::pair<void *, std::pair<OwnerTy, uint64_t>>;
 337   SmallVector<UseTy, 8> Uses(UseMap.begin(), UseMap.end());
 338   llvm::sort(Uses, [](const UseTy &L, const UseTy &R) {
 339     return L.second.second < R.second.second;
 340   });
 341   UseMap.clear();
 342   for (const auto &Pair : Uses) {
 343     auto Owner = Pair.second.first;
 344     if (!Owner)
 345       continue;
 346     if (isa<MetadataAsValue *>(Owner))
 347       continue;
 348
 349     // Resolve MDNodes that point at this.
 350     auto *OwnerMD = dyn_cast_if_present<MDNode>(cast<Metadata *>(Owner));
 351     if (!OwnerMD)
 352       continue;
 353     if (OwnerMD->isResolved())
 354       continue;
 355     OwnerMD->decrementUnresolvedOperandCount();
 356   }
 357 }
 358
 359 ReplaceableMetadataImpl *ReplaceableMetadataImpl::getOrCreate(Metadata &MD) {
 360   if (auto *N = dyn_cast<MDNode>(&MD))
 361     return N->isResolved() ? nullptr : N->Context.getOrCreateReplaceableUses();
 362   return dyn_cast<ValueAsMetadata>(&MD);
 363 }
 364
 365 ReplaceableMetadataImpl *ReplaceableMetadataImpl::getIfExists(Metadata &MD) {
 366   if (auto *N = dyn_cast<MDNode>(&MD))
 367     return N->isResolved() ? nullptr : N->Context.getReplaceableUses();
 368   return dyn_cast<ValueAsMetadata>(&MD);
 369 }
 370
 371 bool ReplaceableMetadataImpl::isReplaceable(const Metadata &MD) {
 372   if (auto *N = dyn_cast<MDNode>(&MD))
 373     return !N->isResolved();
 374   return isa<ValueAsMetadata>(&MD);
 375 }
 376
 377 static DISubprogram *getLocalFunctionMetadata(Value *V) {
 378   assert(V && "Expected value");
 379   if (auto *A = dyn_cast<Argument>(V)) {
 380     if (auto *Fn = A->getParent())
 381       return Fn->getSubprogram();
 382     return nullptr;
 383   }
 384
 385   if (BasicBlock *BB = cast<Instruction>(V)->getParent()) {
 386     if (auto *Fn = BB->getParent())
 387       return Fn->getSubprogram();
 388     return nullptr;
 389   }
 390
 391   return nullptr;
 392 }
 393
 394 ValueAsMetadata *ValueAsMetadata::get(Value *V) {
 395   assert(V && "Unexpected null Value");
 396
 397   auto &Context = V->getContext();
 398   auto *&Entry = Context.pImpl->ValuesAsMetadata[V];
 399   if (!Entry) {
 400     assert((isa<Constant>(V) || isa<Argument>(V) || isa<Instruction>(V)) &&
 401            "Expected constant or function-local value");
 402     assert(!V->IsUsedByMD && "Expected this to be the only metadata use");
 403     V->IsUsedByMD = true;
 404     if (auto *C = dyn_cast<Constant>(V))
 405       Entry = new ConstantAsMetadata(C);
 406     else
 407       Entry = new LocalAsMetadata(V);
 408   }
 409
 410   return Entry;
 411 }
 412
 413 ValueAsMetadata *ValueAsMetadata::getIfExists(Value *V) {
 414   assert(V && "Unexpected null Value");
 415   return V->getContext().pImpl->ValuesAsMetadata.lookup(V);
 416 }
 417
 418 void ValueAsMetadata::handleDeletion(Value *V) {
 419   assert(V && "Expected valid value");
 420
 421   auto &Store = V->getType()->getContext().pImpl->ValuesAsMetadata;
 422   auto I = Store.find(V);
 423   if (I == Store.end())
 424     return;
 425
 426   // Remove old entry from the map.
 427   ValueAsMetadata *MD = I->second;
 428   assert(MD && "Expected valid metadata");
 429   assert(MD->getValue() == V && "Expected valid mapping");
 430   Store.erase(I);
 431
 432   // Delete the metadata.
 433   MD->replaceAllUsesWith(nullptr);
 434   delete MD;
 435 }
 436
 437 void ValueAsMetadata::handleRAUW(Value *From, Value *To) {
 438   assert(From && "Expected valid value");
 439   assert(To && "Expected valid value");
 440   assert(From != To && "Expected changed value");
 441   assert(From->getType() == To->getType() && "Unexpected type change");
 442
 443   LLVMContext &Context = From->getType()->getContext();
 444   auto &Store = Context.pImpl->ValuesAsMetadata;
 445   auto I = Store.find(From);
 446   if (I == Store.end()) {
 447     assert(!From->IsUsedByMD && "Expected From not to be used by metadata");
 448     return;
 449   }
 450
 451   // Remove old entry from the map.
 452   assert(From->IsUsedByMD && "Expected From to be used by metadata");
 453   From->IsUsedByMD = false;
 454   ValueAsMetadata *MD = I->second;
 455   assert(MD && "Expected valid metadata");
 456   assert(MD->getValue() == From && "Expected valid mapping");
 457   Store.erase(I);
 458
 459   if (isa<LocalAsMetadata>(MD)) {
 460     if (auto *C = dyn_cast<Constant>(To)) {
 461       // Local became a constant.
 462       MD->replaceAllUsesWith(ConstantAsMetadata::get(C));
 463       delete MD;
 464       return;
 465     }
 466     if (getLocalFunctionMetadata(From) && getLocalFunctionMetadata(To) &&
 467         getLocalFunctionMetadata(From) != getLocalFunctionMetadata(To)) {
 468       // DISubprogram changed.
 469       MD->replaceAllUsesWith(nullptr);
 470       delete MD;
 471       return;
 472     }
 473   } else if (!isa<Constant>(To)) {
 474     // Changed to function-local value.
 475     MD->replaceAllUsesWith(nullptr);
 476     delete MD;
 477     return;
 478   }
 479
 480   auto *&Entry = Store[To];
 481   if (Entry) {
 482     // The target already exists.
 483     MD->replaceAllUsesWith(Entry);
 484     delete MD;
 485     return;
 486   }
 487
 488   // Update MD in place (and update the map entry).
 489   assert(!To->IsUsedByMD && "Expected this to be the only metadata use");
 490   To->IsUsedByMD = true;
 491   MD->V = To;
 492   Entry = MD;
 493 }
 494
 495 //===----------------------------------------------------------------------===//
 496 // MDString implementation.
 497 //
 498
 499 MDString *MDString::get(LLVMContext &Context, StringRef Str) {
 500   auto &Store = Context.pImpl->MDStringCache;
 501   auto I = Store.try_emplace(Str);
 502   auto &MapEntry = I.first->getValue();
 503   if (!I.second)
 504     return &MapEntry;
 505   MapEntry.Entry = &*I.first;
 506   return &MapEntry;
 507 }
 508
 509 StringRef MDString::getString() const {
 510   assert(Entry && "Expected to find string map entry");
 511   return Entry->first();
 512 }
 513
 514 //===----------------------------------------------------------------------===//
 515 // MDNode implementation.
 516 //
 517
 518 // Assert that the MDNode types will not be unaligned by the objects
 519 // prepended to them.
 520 #define HANDLE_MDNODE_LEAF(CLASS)                                              \
 521   static_assert(                                                               \
 522       alignof(uint64_t) >= alignof(CLASS),                                     \
 523       "Alignment is insufficient after objects prepended to " #CLASS);
 524 #include "llvm/IR/Metadata.def"
 525
 526 void *MDNode::operator new(size_t Size, size_t NumOps, StorageType Storage) {
 527   // uint64_t is the most aligned type we need support (ensured by static_assert
 528   // above)
 529   size_t AllocSize =
 530       alignTo(Header::getAllocSize(Storage, NumOps), alignof(uint64_t));
 531   char *Mem = reinterpret_cast<char *>(::operator new(AllocSize + Size));
 532   Header *H = new (Mem + AllocSize - sizeof(Header)) Header(NumOps, Storage);
 533   return reinterpret_cast<void *>(H + 1);
 534 }
 535
 536 void MDNode::operator delete(void *N) {
 537   Header *H = reinterpret_cast<Header *>(N) - 1;
 538   void *Mem = H->getAllocation();
 539   H->~Header();
 540   ::operator delete(Mem);
 541 }
 542
 543 MDNode::MDNode(LLVMContext &Context, unsigned ID, StorageType Storage,
 544                ArrayRef<Metadata *> Ops1, ArrayRef<Metadata *> Ops2)
 545     : Metadata(ID, Storage), Context(Context) {
 546   unsigned Op = 0;
 547   for (Metadata *MD : Ops1)
 548     setOperand(Op++, MD);
 549   for (Metadata *MD : Ops2)
 550     setOperand(Op++, MD);
 551
 552   if (!isUniqued())
 553     return;
 554
 555   // Count the unresolved operands.  If there are any, RAUW support will be
 556   // added lazily on first reference.
 557   countUnresolvedOperands();
 558 }
 559
 560 TempMDNode MDNode::clone() const {
 561   switch (getMetadataID()) {
 562   default:
 563     llvm_unreachable("Invalid MDNode subclass");
 564 #define HANDLE_MDNODE_LEAF(CLASS)                                              \
 565   case CLASS##Kind:                                                            \
 566     return cast<CLASS>(this)->cloneImpl();
 567 #include "llvm/IR/Metadata.def"
 568   }
 569 }
 570
 571 MDNode::Header::Header(size_t NumOps, StorageType Storage) {
 572   IsLarge = isLarge(NumOps);
 573   IsResizable = isResizable(Storage);
 574   SmallSize = getSmallSize(NumOps, IsResizable, IsLarge);
 575   if (IsLarge) {
 576     SmallNumOps = 0;
 577     new (getLargePtr()) LargeStorageVector();
 578     getLarge().resize(NumOps);
 579     return;
 580   }
 581   SmallNumOps = NumOps;
 582   MDOperand *O = reinterpret_cast<MDOperand *>(this) - SmallSize;
 583   for (MDOperand *E = O + SmallSize; O != E;)
 584     (void)new (O++) MDOperand();
 585 }
 586
 587 MDNode::Header::~Header() {
 588   if (IsLarge) {
 589     getLarge().~LargeStorageVector();
 590     return;
 591   }
 592   MDOperand *O = reinterpret_cast<MDOperand *>(this);
 593   for (MDOperand *E = O - SmallSize; O != E; --O)
 594     (void)(O - 1)->~MDOperand();
 595 }
 596
 597 void *MDNode::Header::getSmallPtr() {
 598   static_assert(alignof(MDOperand) <= alignof(Header),
 599                 "MDOperand too strongly aligned");
 600   return reinterpret_cast<char *>(const_cast<Header *>(this)) -
 601          sizeof(MDOperand) * SmallSize;
 602 }
 603
 604 void MDNode::Header::resize(size_t NumOps) {
 605   assert(IsResizable && "Node is not resizable");
 606   if (operands().size() == NumOps)
 607     return;
 608
 609   if (IsLarge)
 610     getLarge().resize(NumOps);
 611   else if (NumOps <= SmallSize)
 612     resizeSmall(NumOps);
 613   else
 614     resizeSmallToLarge(NumOps);
 615 }
 616
 617 void MDNode::Header::resizeSmall(size_t NumOps) {
 618   assert(!IsLarge && "Expected a small MDNode");
 619   assert(NumOps <= SmallSize && "NumOps too large for small resize");
 620
 621   MutableArrayRef<MDOperand> ExistingOps = operands();
 622   assert(NumOps != ExistingOps.size() && "Expected a different size");
 623
 624   int NumNew = (int)NumOps - (int)ExistingOps.size();
 625   MDOperand *O = ExistingOps.end();
 626   for (int I = 0, E = NumNew; I < E; ++I)
 627     (O++)->reset();
 628   for (int I = 0, E = NumNew; I > E; --I)
 629     (--O)->reset();
 630   SmallNumOps = NumOps;
 631   assert(O == operands().end() && "Operands not (un)initialized until the end");
 632 }
 633
 634 void MDNode::Header::resizeSmallToLarge(size_t NumOps) {
 635   assert(!IsLarge && "Expected a small MDNode");
 636   assert(NumOps > SmallSize && "Expected NumOps to be larger than allocation");
 637   LargeStorageVector NewOps;
 638   NewOps.resize(NumOps);
 639   llvm::move(operands(), NewOps.begin());
 640   resizeSmall(0);
 641   new (getLargePtr()) LargeStorageVector(std::move(NewOps));
 642   IsLarge = true;
 643 }
 644
 645 static bool isOperandUnresolved(Metadata *Op) {
 646   if (auto *N = dyn_cast_or_null<MDNode>(Op))
 647     return !N->isResolved();
 648   return false;
 649 }
 650
 651 void MDNode::countUnresolvedOperands() {
 652   assert(getNumUnresolved() == 0 && "Expected unresolved ops to be uncounted");
 653   assert(isUniqued() && "Expected this to be uniqued");
 654   setNumUnresolved(count_if(operands(), isOperandUnresolved));
 655 }
 656
 657 void MDNode::makeUniqued() {
 658   assert(isTemporary() && "Expected this to be temporary");
 659   assert(!isResolved() && "Expected this to be unresolved");
 660
 661   // Enable uniquing callbacks.
 662   for (auto &Op : mutable_operands())
 663     Op.reset(Op.get(), this);
 664
 665   // Make this 'uniqued'.
 666   Storage = Uniqued;
 667   countUnresolvedOperands();
 668   if (!getNumUnresolved()) {
 669     dropReplaceableUses();
 670     assert(isResolved() && "Expected this to be resolved");
 671   }
 672
 673   assert(isUniqued() && "Expected this to be uniqued");
 674 }
 675
 676 void MDNode::makeDistinct() {
 677   assert(isTemporary() && "Expected this to be temporary");
 678   assert(!isResolved() && "Expected this to be unresolved");
 679
 680   // Drop RAUW support and store as a distinct node.
 681   dropReplaceableUses();
 682   storeDistinctInContext();
 683
 684   assert(isDistinct() && "Expected this to be distinct");
 685   assert(isResolved() && "Expected this to be resolved");
 686 }
 687
 688 void MDNode::resolve() {
 689   assert(isUniqued() && "Expected this to be uniqued");
 690   assert(!isResolved() && "Expected this to be unresolved");
 691
 692   setNumUnresolved(0);
 693   dropReplaceableUses();
 694
 695   assert(isResolved() && "Expected this to be resolved");
 696 }
 697
 698 void MDNode::dropReplaceableUses() {
 699   assert(!getNumUnresolved() && "Unexpected unresolved operand");
 700
 701   // Drop any RAUW support.
 702   if (Context.hasReplaceableUses())
 703     Context.takeReplaceableUses()->resolveAllUses();
 704 }
 705
 706 void MDNode::resolveAfterOperandChange(Metadata *Old, Metadata *New) {
 707   assert(isUniqued() && "Expected this to be uniqued");
 708   assert(getNumUnresolved() != 0 && "Expected unresolved operands");
 709
 710   // Check if an operand was resolved.
 711   if (!isOperandUnresolved(Old)) {
 712     if (isOperandUnresolved(New))
 713       // An operand was un-resolved!
 714       setNumUnresolved(getNumUnresolved() + 1);
 715   } else if (!isOperandUnresolved(New))
 716     decrementUnresolvedOperandCount();
 717 }
 718
 719 void MDNode::decrementUnresolvedOperandCount() {
 720   assert(!isResolved() && "Expected this to be unresolved");
 721   if (isTemporary())
 722     return;
 723
 724   assert(isUniqued() && "Expected this to be uniqued");
 725   setNumUnresolved(getNumUnresolved() - 1);
 726   if (getNumUnresolved())
 727     return;
 728
 729   // Last unresolved operand has just been resolved.
 730   dropReplaceableUses();
 731   assert(isResolved() && "Expected this to become resolved");
 732 }
 733
 734 void MDNode::resolveCycles() {
 735   if (isResolved())
 736     return;
 737
 738   // Resolve this node immediately.
 739   resolve();
 740
 741   // Resolve all operands.
 742   for (const auto &Op : operands()) {
 743     auto *N = dyn_cast_or_null<MDNode>(Op);
 744     if (!N)
 745       continue;
 746
 747     assert(!N->isTemporary() &&
 748            "Expected all forward declarations to be resolved");
 749     if (!N->isResolved())
 750       N->resolveCycles();
 751   }
 752 }
 753
 754 static bool hasSelfReference(MDNode *N) {
 755   return llvm::is_contained(N->operands(), N);
 756 }
 757
 758 MDNode *MDNode::replaceWithPermanentImpl() {
 759   switch (getMetadataID()) {
 760   default:
 761     // If this type isn't uniquable, replace with a distinct node.
 762     return replaceWithDistinctImpl();
 763
 764 #define HANDLE_MDNODE_LEAF_UNIQUABLE(CLASS)                                    \
 765   case CLASS##Kind:                                                            \
 766     break;
 767 #include "llvm/IR/Metadata.def"
 768   }
 769
 770   // Even if this type is uniquable, self-references have to be distinct.
 771   if (hasSelfReference(this))
 772     return replaceWithDistinctImpl();
 773   return replaceWithUniquedImpl();
 774 }
 775
 776 MDNode *MDNode::replaceWithUniquedImpl() {
 777   // Try to uniquify in place.
 778   MDNode *UniquedNode = uniquify();
 779
 780   if (UniquedNode == this) {
 781     makeUniqued();
 782     return this;
 783   }
 784
 785   // Collision, so RAUW instead.
 786   replaceAllUsesWith(UniquedNode);
 787   deleteAsSubclass();
 788   return UniquedNode;
 789 }
 790
 791 MDNode *MDNode::replaceWithDistinctImpl() {
 792   makeDistinct();
 793   return this;
 794 }
 795
 796 void MDTuple::recalculateHash() {
 797   setHash(MDTupleInfo::KeyTy::calculateHash(this));
 798 }
 799
 800 void MDNode::dropAllReferences() {
 801   for (unsigned I = 0, E = getNumOperands(); I != E; ++I)
 802     setOperand(I, nullptr);
 803   if (Context.hasReplaceableUses()) {
 804     Context.getReplaceableUses()->resolveAllUses(/* ResolveUsers */ false);
 805     (void)Context.takeReplaceableUses();
 806   }
 807 }
 808
 809 void MDNode::handleChangedOperand(void *Ref, Metadata *New) {
 810   unsigned Op = static_cast<MDOperand *>(Ref) - op_begin();
 811   assert(Op < getNumOperands() && "Expected valid operand");
 812
 813   if (!isUniqued()) {
 814     // This node is not uniqued.  Just set the operand and be done with it.
 815     setOperand(Op, New);
 816     return;
 817   }
 818
 819   // This node is uniqued.
 820   eraseFromStore();
 821
 822   Metadata *Old = getOperand(Op);
 823   setOperand(Op, New);
 824
 825   // Drop uniquing for self-reference cycles and deleted constants.
 826   if (New == this || (!New && Old && isa<ConstantAsMetadata>(Old))) {
 827     if (!isResolved())
 828       resolve();
 829     storeDistinctInContext();
 830     return;
 831   }
 832
 833   // Re-unique the node.
 834   auto *Uniqued = uniquify();
 835   if (Uniqued == this) {
 836     if (!isResolved())
 837       resolveAfterOperandChange(Old, New);
 838     return;
 839   }
 840
 841   // Collision.
 842   if (!isResolved()) {
 843     // Still unresolved, so RAUW.
 844     //
 845     // First, clear out all operands to prevent any recursion (similar to
 846     // dropAllReferences(), but we still need the use-list).
 847     for (unsigned O = 0, E = getNumOperands(); O != E; ++O)
 848       setOperand(O, nullptr);
 849     if (Context.hasReplaceableUses())
 850       Context.getReplaceableUses()->replaceAllUsesWith(Uniqued);
 851     deleteAsSubclass();
 852     return;
 853   }
 854
 855   // Store in non-uniqued form if RAUW isn't possible.
 856   storeDistinctInContext();
 857 }
 858
 859 void MDNode::deleteAsSubclass() {
 860   switch (getMetadataID()) {
 861   default:
 862     llvm_unreachable("Invalid subclass of MDNode");
 863 #define HANDLE_MDNODE_LEAF(CLASS)                                              \
 864   case CLASS##Kind:                                                            \
 865     delete cast<CLASS>(this);                                                  \
 866     break;
 867 #include "llvm/IR/Metadata.def"
 868   }
 869 }
 870
 871 template <class T, class InfoT>
 872 static T *uniquifyImpl(T *N, DenseSet<T *, InfoT> &Store) {
 873   if (T *U = getUniqued(Store, N))
 874     return U;
 875
 876   Store.insert(N);
 877   return N;
 878 }
 879
 880 template <class NodeTy> struct MDNode::HasCachedHash {
 881   using Yes = char[1];
 882   using No = char[2];
 883   template <class U, U Val> struct SFINAE {};
 884
 885   template <class U>
 886   static Yes &check(SFINAE<void (U::*)(unsigned), &U::setHash> *);
 887   template <class U> static No &check(...);
 888
 889   static const bool value = sizeof(check<NodeTy>(nullptr)) == sizeof(Yes);
 890 };
 891
 892 MDNode *MDNode::uniquify() {
 893   assert(!hasSelfReference(this) && "Cannot uniquify a self-referencing node");
 894
 895   // Try to insert into uniquing store.
 896   switch (getMetadataID()) {
 897   default:
 898     llvm_unreachable("Invalid or non-uniquable subclass of MDNode");
 899 #define HANDLE_MDNODE_LEAF_UNIQUABLE(CLASS)                                    \
 900   case CLASS##Kind: {                                                          \
 901     CLASS *SubclassThis = cast<CLASS>(this);                                   \
 902     std::integral_constant<bool, HasCachedHash<CLASS>::value>                  \
 903         ShouldRecalculateHash;                                                 \
 904     dispatchRecalculateHash(SubclassThis, ShouldRecalculateHash);              \
 905     return uniquifyImpl(SubclassThis, getContext().pImpl->CLASS##s);           \
 906   }
 907 #include "llvm/IR/Metadata.def"
 908   }
 909 }
 910
 911 void MDNode::eraseFromStore() {
 912   switch (getMetadataID()) {
 913   default:
 914     llvm_unreachable("Invalid or non-uniquable subclass of MDNode");
 915 #define HANDLE_MDNODE_LEAF_UNIQUABLE(CLASS)                                    \
 916   case CLASS##Kind:                                                            \
 917     getContext().pImpl->CLASS##s.erase(cast<CLASS>(this));                     \
 918     break;
 919 #include "llvm/IR/Metadata.def"
 920   }
 921 }
 922
 923 MDTuple *MDTuple::getImpl(LLVMContext &Context, ArrayRef<Metadata *> MDs,
 924                           StorageType Storage, bool ShouldCreate) {
 925   unsigned Hash = 0;
 926   if (Storage == Uniqued) {
 927     MDTupleInfo::KeyTy Key(MDs);
 928     if (auto *N = getUniqued(Context.pImpl->MDTuples, Key))
 929       return N;
 930     if (!ShouldCreate)
 931       return nullptr;
 932     Hash = Key.getHash();
 933   } else {
 934     assert(ShouldCreate && "Expected non-uniqued nodes to always be created");
 935   }
 936
 937   return storeImpl(new (MDs.size(), Storage)
 938                        MDTuple(Context, Storage, Hash, MDs),
 939                    Storage, Context.pImpl->MDTuples);
 940 }
 941
 942 void MDNode::deleteTemporary(MDNode *N) {
 943   assert(N->isTemporary() && "Expected temporary node");
 944   N->replaceAllUsesWith(nullptr);
 945   N->deleteAsSubclass();
 946 }
 947
 948 void MDNode::storeDistinctInContext() {
 949   assert(!Context.hasReplaceableUses() && "Unexpected replaceable uses");
 950   assert(!getNumUnresolved() && "Unexpected unresolved nodes");
 951   Storage = Distinct;
 952   assert(isResolved() && "Expected this to be resolved");
 953
 954   // Reset the hash.
 955   switch (getMetadataID()) {
 956   default:
 957     llvm_unreachable("Invalid subclass of MDNode");
 958 #define HANDLE_MDNODE_LEAF(CLASS)                                              \
 959   case CLASS##Kind: {                                                          \
 960     std::integral_constant<bool, HasCachedHash<CLASS>::value> ShouldResetHash; \
 961     dispatchResetHash(cast<CLASS>(this), ShouldResetHash);                     \
 962     break;                                                                     \
 963   }
 964 #include "llvm/IR/Metadata.def"
 965   }
 966
 967   getContext().pImpl->DistinctMDNodes.push_back(this);
 968 }
 969
 970 void MDNode::replaceOperandWith(unsigned I, Metadata *New) {
 971   if (getOperand(I) == New)
 972     return;
 973
 974   if (!isUniqued()) {
 975     setOperand(I, New);
 976     return;
 977   }
 978
 979   handleChangedOperand(mutable_begin() + I, New);
 980 }
 981
 982 void MDNode::setOperand(unsigned I, Metadata *New) {
 983   assert(I < getNumOperands());
 984   mutable_begin()[I].reset(New, isUniqued() ? this : nullptr);
 985 }
 986
 987 /// Get a node or a self-reference that looks like it.
 988 ///
 989 /// Special handling for finding self-references, for use by \a
 990 /// MDNode::concatenate() and \a MDNode::intersect() to maintain behaviour from
 991 /// when self-referencing nodes were still uniqued.  If the first operand has
 992 /// the same operands as \c Ops, return the first operand instead.
 993 static MDNode *getOrSelfReference(LLVMContext &Context,
 994                                   ArrayRef<Metadata *> Ops) {
 995   if (!Ops.empty())
 996     if (MDNode *N = dyn_cast_or_null<MDNode>(Ops[0]))
 997       if (N->getNumOperands() == Ops.size() && N == N->getOperand(0)) {
 998         for (unsigned I = 1, E = Ops.size(); I != E; ++I)
 999           if (Ops[I] != N->getOperand(I))
1000             return MDNode::get(Context, Ops);
1001         return N;
1002       }
1003
1004   return MDNode::get(Context, Ops);
1005 }
1006
1007 MDNode *MDNode::concatenate(MDNode *A, MDNode *B) {
1008   if (!A)
1009     return B;
1010   if (!B)
1011     return A;
1012
1013   SmallSetVector<Metadata *, 4> MDs(A->op_begin(), A->op_end());
1014   MDs.insert(B->op_begin(), B->op_end());
1015
1016   // FIXME: This preserves long-standing behaviour, but is it really the right
1017   // behaviour?  Or was that an unintended side-effect of node uniquing?
1018   return getOrSelfReference(A->getContext(), MDs.getArrayRef());
1019 }
1020
1021 MDNode *MDNode::intersect(MDNode *A, MDNode *B) {
1022   if (!A || !B)
1023     return nullptr;
1024
1025   SmallSetVector<Metadata *, 4> MDs(A->op_begin(), A->op_end());
1026   SmallPtrSet<Metadata *, 4> BSet(B->op_begin(), B->op_end());
1027   MDs.remove_if([&](Metadata *MD) { return !BSet.count(MD); });
1028
1029   // FIXME: This preserves long-standing behaviour, but is it really the right
1030   // behaviour?  Or was that an unintended side-effect of node uniquing?
1031   return getOrSelfReference(A->getContext(), MDs.getArrayRef());
1032 }
1033
1034 MDNode *MDNode::getMostGenericAliasScope(MDNode *A, MDNode *B) {
1035   if (!A || !B)
1036     return nullptr;
1037
1038   // Take the intersection of domains then union the scopes
1039   // within those domains
1040   SmallPtrSet<const MDNode *, 16> ADomains;
1041   SmallPtrSet<const MDNode *, 16> IntersectDomains;
1042   SmallSetVector<Metadata *, 4> MDs;
1043   for (const MDOperand &MDOp : A->operands())
1044     if (const MDNode *NAMD = dyn_cast<MDNode>(MDOp))
1045       if (const MDNode *Domain = AliasScopeNode(NAMD).getDomain())
1046         ADomains.insert(Domain);
1047
1048   for (const MDOperand &MDOp : B->operands())
1049     if (const MDNode *NAMD = dyn_cast<MDNode>(MDOp))
1050       if (const MDNode *Domain = AliasScopeNode(NAMD).getDomain())
1051         if (ADomains.contains(Domain)) {
1052           IntersectDomains.insert(Domain);
1053           MDs.insert(MDOp);
1054         }
1055
1056   for (const MDOperand &MDOp : A->operands())
1057     if (const MDNode *NAMD = dyn_cast<MDNode>(MDOp))
1058       if (const MDNode *Domain = AliasScopeNode(NAMD).getDomain())
1059         if (IntersectDomains.contains(Domain))
1060           MDs.insert(MDOp);
1061
1062   return MDs.empty() ? nullptr
1063                      : getOrSelfReference(A->getContext(), MDs.getArrayRef());
1064 }
1065
1066 MDNode *MDNode::getMostGenericFPMath(MDNode *A, MDNode *B) {
1067   if (!A || !B)
1068     return nullptr;
1069
1070   APFloat AVal = mdconst::extract<ConstantFP>(A->getOperand(0))->getValueAPF();
1071   APFloat BVal = mdconst::extract<ConstantFP>(B->getOperand(0))->getValueAPF();
1072   if (AVal < BVal)
1073     return A;
1074   return B;
1075 }
1076
1077 // Call instructions with branch weights are only used in SamplePGO as
1078 // documented in
1079 /// https://llvm.org/docs/BranchWeightMetadata.html#callinst).
1080 MDNode *MDNode::mergeDirectCallProfMetadata(MDNode *A, MDNode *B,
1081                                             const Instruction *AInstr,
1082                                             const Instruction *BInstr) {
1083   assert(A && B && AInstr && BInstr && "Caller should guarantee");
1084   auto &Ctx = AInstr->getContext();
1085   MDBuilder MDHelper(Ctx);
1086
1087   // LLVM IR verifier verifies !prof metadata has at least 2 operands.
1088   assert(A->getNumOperands() >= 2 && B->getNumOperands() >= 2 &&
1089          "!prof annotations should have no less than 2 operands");
1090   MDString *AMDS = dyn_cast<MDString>(A->getOperand(0));
1091   MDString *BMDS = dyn_cast<MDString>(B->getOperand(0));
1092   // LLVM IR verfier verifies first operand is MDString.
1093   assert(AMDS != nullptr && BMDS != nullptr &&
1094          "first operand should be a non-null MDString");
1095   StringRef AProfName = AMDS->getString();
1096   StringRef BProfName = BMDS->getString();
1097   if (AProfName.equals("branch_weights") &&
1098       BProfName.equals("branch_weights")) {
1099     ConstantInt *AInstrWeight =
1100         mdconst::dyn_extract<ConstantInt>(A->getOperand(1));
1101     ConstantInt *BInstrWeight =
1102         mdconst::dyn_extract<ConstantInt>(B->getOperand(1));
1103     assert(AInstrWeight && BInstrWeight && "verified by LLVM verifier");
1104     return MDNode::get(Ctx,
1105                        {MDHelper.createString("branch_weights"),
1106                         MDHelper.createConstant(ConstantInt::get(
1107                             Type::getInt64Ty(Ctx),
1108                             SaturatingAdd(AInstrWeight->getZExtValue(),
1109                                           BInstrWeight->getZExtValue())))});
1110   }
1111   return nullptr;
1112 }
1113
1114 // Pass in both instructions and nodes. Instruction information (e.g.,
1115 // instruction type) helps interpret profiles and make implementation clearer.
1116 MDNode *MDNode::getMergedProfMetadata(MDNode *A, MDNode *B,
1117                                       const Instruction *AInstr,
1118                                       const Instruction *BInstr) {
1119   if (!(A && B)) {
1120     return A ? A : B;
1121   }
1122
1123   assert(AInstr->getMetadata(LLVMContext::MD_prof) == A &&
1124          "Caller should guarantee");
1125   assert(BInstr->getMetadata(LLVMContext::MD_prof) == B &&
1126          "Caller should guarantee");
1127
1128   const CallInst *ACall = dyn_cast<CallInst>(AInstr);
1129   const CallInst *BCall = dyn_cast<CallInst>(BInstr);
1130
1131   // Both ACall and BCall are direct callsites.
1132   if (ACall && BCall && ACall->getCalledFunction() &&
1133       BCall->getCalledFunction())
1134     return mergeDirectCallProfMetadata(A, B, AInstr, BInstr);
1135
1136   // The rest of the cases are not implemented but could be added
1137   // when there are use cases.
1138   return nullptr;
1139 }
1140
1141 static bool isContiguous(const ConstantRange &A, const ConstantRange &B) {
1142   return A.getUpper() == B.getLower() || A.getLower() == B.getUpper();
1143 }
1144
1145 static bool canBeMerged(const ConstantRange &A, const ConstantRange &B) {
1146   return !A.intersectWith(B).isEmptySet() || isContiguous(A, B);
1147 }
1148
1149 static bool tryMergeRange(SmallVectorImpl<ConstantInt *> &EndPoints,
1150                           ConstantInt *Low, ConstantInt *High) {
1151   ConstantRange NewRange(Low->getValue(), High->getValue());
1152   unsigned Size = EndPoints.size();
1153   APInt LB = EndPoints[Size - 2]->getValue();
1154   APInt LE = EndPoints[Size - 1]->getValue();
1155   ConstantRange LastRange(LB, LE);
1156   if (canBeMerged(NewRange, LastRange)) {
1157     ConstantRange Union = LastRange.unionWith(NewRange);
1158     Type *Ty = High->getType();
1159     EndPoints[Size - 2] =
1160         cast<ConstantInt>(ConstantInt::get(Ty, Union.getLower()));
1161     EndPoints[Size - 1] =
1162         cast<ConstantInt>(ConstantInt::get(Ty, Union.getUpper()));
1163     return true;
1164   }
1165   return false;
1166 }
1167
1168 static void addRange(SmallVectorImpl<ConstantInt *> &EndPoints,
1169                      ConstantInt *Low, ConstantInt *High) {
1170   if (!EndPoints.empty())
1171     if (tryMergeRange(EndPoints, Low, High))
1172       return;
1173
1174   EndPoints.push_back(Low);
1175   EndPoints.push_back(High);
1176 }
1177
1178 MDNode *MDNode::getMostGenericRange(MDNode *A, MDNode *B) {
1179   // Given two ranges, we want to compute the union of the ranges. This
1180   // is slightly complicated by having to combine the intervals and merge
1181   // the ones that overlap.
1182
1183   if (!A || !B)
1184     return nullptr;
1185
1186   if (A == B)
1187     return A;
1188
1189   // First, walk both lists in order of the lower boundary of each interval.
1190   // At each step, try to merge the new interval to the last one we adedd.
1191   SmallVector<ConstantInt *, 4> EndPoints;
1192   int AI = 0;
1193   int BI = 0;
1194   int AN = A->getNumOperands() / 2;
1195   int BN = B->getNumOperands() / 2;
1196   while (AI < AN && BI < BN) {
1197     ConstantInt *ALow = mdconst::extract<ConstantInt>(A->getOperand(2 * AI));
1198     ConstantInt *BLow = mdconst::extract<ConstantInt>(B->getOperand(2 * BI));
1199
1200     if (ALow->getValue().slt(BLow->getValue())) {
1201       addRange(EndPoints, ALow,
1202                mdconst::extract<ConstantInt>(A->getOperand(2 * AI + 1)));
1203       ++AI;
1204     } else {
1205       addRange(EndPoints, BLow,
1206                mdconst::extract<ConstantInt>(B->getOperand(2 * BI + 1)));
1207       ++BI;
1208     }
1209   }
1210   while (AI < AN) {
1211     addRange(EndPoints, mdconst::extract<ConstantInt>(A->getOperand(2 * AI)),
1212              mdconst::extract<ConstantInt>(A->getOperand(2 * AI + 1)));
1213     ++AI;
1214   }
1215   while (BI < BN) {
1216     addRange(EndPoints, mdconst::extract<ConstantInt>(B->getOperand(2 * BI)),
1217              mdconst::extract<ConstantInt>(B->getOperand(2 * BI + 1)));
1218     ++BI;
1219   }
1220
1221   // If we have more than 2 ranges (4 endpoints) we have to try to merge
1222   // the last and first ones.
1223   unsigned Size = EndPoints.size();
1224   if (Size > 4) {
1225     ConstantInt *FB = EndPoints[0];
1226     ConstantInt *FE = EndPoints[1];
1227     if (tryMergeRange(EndPoints, FB, FE)) {
1228       for (unsigned i = 0; i < Size - 2; ++i) {
1229         EndPoints[i] = EndPoints[i + 2];
1230       }
1231       EndPoints.resize(Size - 2);
1232     }
1233   }
1234
1235   // If in the end we have a single range, it is possible that it is now the
1236   // full range. Just drop the metadata in that case.
1237   if (EndPoints.size() == 2) {
1238     ConstantRange Range(EndPoints[0]->getValue(), EndPoints[1]->getValue());
1239     if (Range.isFullSet())
1240       return nullptr;
1241   }
1242
1243   SmallVector<Metadata *, 4> MDs;
1244   MDs.reserve(EndPoints.size());
1245   for (auto *I : EndPoints)
1246     MDs.push_back(ConstantAsMetadata::get(I));
1247   return MDNode::get(A->getContext(), MDs);
1248 }
1249
1250 MDNode *MDNode::getMostGenericAlignmentOrDereferenceable(MDNode *A, MDNode *B) {
1251   if (!A || !B)
1252     return nullptr;
1253
1254   ConstantInt *AVal = mdconst::extract<ConstantInt>(A->getOperand(0));
1255   ConstantInt *BVal = mdconst::extract<ConstantInt>(B->getOperand(0));
1256   if (AVal->getZExtValue() < BVal->getZExtValue())
1257     return A;
1258   return B;
1259 }
1260
1261 //===----------------------------------------------------------------------===//
1262 // NamedMDNode implementation.
1263 //
1264
1265 static SmallVector<TrackingMDRef, 4> &getNMDOps(void *Operands) {
1266   return *(SmallVector<TrackingMDRef, 4> *)Operands;
1267 }
1268
1269 NamedMDNode::NamedMDNode(const Twine &N)
1270     : Name(N.str()), Operands(new SmallVector<TrackingMDRef, 4>()) {}
1271
1272 NamedMDNode::~NamedMDNode() {
1273   dropAllReferences();
1274   delete &getNMDOps(Operands);
1275 }
1276
1277 unsigned NamedMDNode::getNumOperands() const {
1278   return (unsigned)getNMDOps(Operands).size();
1279 }
1280
1281 MDNode *NamedMDNode::getOperand(unsigned i) const {
1282   assert(i < getNumOperands() && "Invalid Operand number!");
1283   auto *N = getNMDOps(Operands)[i].get();
1284   return cast_or_null<MDNode>(N);
1285 }
1286
1287 void NamedMDNode::addOperand(MDNode *M) { getNMDOps(Operands).emplace_back(M); }
1288
1289 void NamedMDNode::setOperand(unsigned I, MDNode *New) {
1290   assert(I < getNumOperands() && "Invalid operand number");
1291   getNMDOps(Operands)[I].reset(New);
1292 }
1293
1294 void NamedMDNode::eraseFromParent() { getParent()->eraseNamedMetadata(this); }
1295
1296 void NamedMDNode::clearOperands() { getNMDOps(Operands).clear(); }
1297
1298 StringRef NamedMDNode::getName() const { return StringRef(Name); }
1299
1300 //===----------------------------------------------------------------------===//
1301 // Instruction Metadata method implementations.
1302 //
1303
1304 MDNode *MDAttachments::lookup(unsigned ID) const {
1305   for (const auto &A : Attachments)
1306     if (A.MDKind == ID)
1307       return A.Node;
1308   return nullptr;
1309 }
1310
1311 void MDAttachments::get(unsigned ID, SmallVectorImpl<MDNode *> &Result) const {
1312   for (const auto &A : Attachments)
1313     if (A.MDKind == ID)
1314       Result.push_back(A.Node);
1315 }
1316
1317 void MDAttachments::getAll(
1318     SmallVectorImpl<std::pair<unsigned, MDNode *>> &Result) const {
1319   for (const auto &A : Attachments)
1320     Result.emplace_back(A.MDKind, A.Node);
1321
1322   // Sort the resulting array so it is stable with respect to metadata IDs. We
1323   // need to preserve the original insertion order though.
1324   if (Result.size() > 1)
1325     llvm::stable_sort(Result, less_first());
1326 }
1327
1328 void MDAttachments::set(unsigned ID, MDNode *MD) {
1329   erase(ID);
1330   if (MD)
1331     insert(ID, *MD);
1332 }
1333
1334 void MDAttachments::insert(unsigned ID, MDNode &MD) {
1335   Attachments.push_back({ID, TrackingMDNodeRef(&MD)});
1336 }
1337
1338 bool MDAttachments::erase(unsigned ID) {
1339   if (empty())
1340     return false;
1341
1342   // Common case is one value.
1343   if (Attachments.size() == 1 && Attachments.back().MDKind == ID) {
1344     Attachments.pop_back();
1345     return true;
1346   }
1347
1348   auto OldSize = Attachments.size();
1349   llvm::erase_if(Attachments,
1350                  [ID](const Attachment &A) { return A.MDKind == ID; });
1351   return OldSize != Attachments.size();
1352 }
1353
1354 MDNode *Value::getMetadata(StringRef Kind) const {
1355   if (!hasMetadata())
1356     return nullptr;
1357   unsigned KindID = getContext().getMDKindID(Kind);
1358   return getMetadataImpl(KindID);
1359 }
1360
1361 MDNode *Value::getMetadataImpl(unsigned KindID) const {
1362   const LLVMContext &Ctx = getContext();
1363   const MDAttachments &Attachements = Ctx.pImpl->ValueMetadata.at(this);
1364   return Attachements.lookup(KindID);
1365 }
1366
1367 void Value::getMetadata(unsigned KindID, SmallVectorImpl<MDNode *> &MDs) const {
1368   if (hasMetadata())
1369     getContext().pImpl->ValueMetadata.at(this).get(KindID, MDs);
1370 }
1371
1372 void Value::getMetadata(StringRef Kind, SmallVectorImpl<MDNode *> &MDs) const {
1373   if (hasMetadata())
1374     getMetadata(getContext().getMDKindID(Kind), MDs);
1375 }
1376
1377 void Value::getAllMetadata(
1378     SmallVectorImpl<std::pair<unsigned, MDNode *>> &MDs) const {
1379   if (hasMetadata()) {
1380     assert(getContext().pImpl->ValueMetadata.count(this) &&
1381            "bit out of sync with hash table");
1382     const MDAttachments &Info = getContext().pImpl->ValueMetadata.at(this);
1383     Info.getAll(MDs);
1384   }
1385 }
1386
1387 void Value::setMetadata(unsigned KindID, MDNode *Node) {
1388   assert(isa<Instruction>(this) || isa<GlobalObject>(this));
1389
1390   // Handle the case when we're adding/updating metadata on a value.
1391   if (Node) {
1392     MDAttachments &Info = getContext().pImpl->ValueMetadata[this];
1393     assert(!Info.empty() == HasMetadata && "bit out of sync with hash table");
1394     if (Info.empty())
1395       HasMetadata = true;
1396     Info.set(KindID, Node);
1397     return;
1398   }
1399
1400   // Otherwise, we're removing metadata from an instruction.
1401   assert((HasMetadata == (getContext().pImpl->ValueMetadata.count(this) > 0)) &&
1402          "bit out of sync with hash table");
1403   if (!HasMetadata)
1404     return; // Nothing to remove!
1405   MDAttachments &Info = getContext().pImpl->ValueMetadata.find(this)->second;
1406
1407   // Handle removal of an existing value.
1408   Info.erase(KindID);
1409   if (!Info.empty())
1410     return;
1411   getContext().pImpl->ValueMetadata.erase(this);
1412   HasMetadata = false;
1413 }
1414
1415 void Value::setMetadata(StringRef Kind, MDNode *Node) {
1416   if (!Node && !HasMetadata)
1417     return;
1418   setMetadata(getContext().getMDKindID(Kind), Node);
1419 }
1420
1421 void Value::addMetadata(unsigned KindID, MDNode &MD) {
1422   assert(isa<Instruction>(this) || isa<GlobalObject>(this));
1423   if (!HasMetadata)
1424     HasMetadata = true;
1425   getContext().pImpl->ValueMetadata[this].insert(KindID, MD);
1426 }
1427
1428 void Value::addMetadata(StringRef Kind, MDNode &MD) {
1429   addMetadata(getContext().getMDKindID(Kind), MD);
1430 }
1431
1432 bool Value::eraseMetadata(unsigned KindID) {
1433   // Nothing to unset.
1434   if (!HasMetadata)
1435     return false;
1436
1437   MDAttachments &Store = getContext().pImpl->ValueMetadata.find(this)->second;
1438   bool Changed = Store.erase(KindID);
1439   if (Store.empty())
1440     clearMetadata();
1441   return Changed;
1442 }
1443
1444 void Value::clearMetadata() {
1445   if (!HasMetadata)
1446     return;
1447   assert(getContext().pImpl->ValueMetadata.count(this) &&
1448          "bit out of sync with hash table");
1449   getContext().pImpl->ValueMetadata.erase(this);
1450   HasMetadata = false;
1451 }
1452
1453 void Instruction::setMetadata(StringRef Kind, MDNode *Node) {
1454   if (!Node && !hasMetadata())
1455     return;
1456   setMetadata(getContext().getMDKindID(Kind), Node);
1457 }
1458
1459 MDNode *Instruction::getMetadataImpl(StringRef Kind) const {
1460   const LLVMContext &Ctx = getContext();
1461   unsigned KindID = Ctx.getMDKindID(Kind);
1462   if (KindID == LLVMContext::MD_dbg)
1463     return DbgLoc.getAsMDNode();
1464   return Value::getMetadata(KindID);
1465 }
1466
1467 void Instruction::dropUnknownNonDebugMetadata(ArrayRef<unsigned> KnownIDs) {
1468   if (!Value::hasMetadata())
1469     return; // Nothing to remove!
1470
1471   SmallSet<unsigned, 4> KnownSet;
1472   KnownSet.insert(KnownIDs.begin(), KnownIDs.end());
1473
1474   // A DIAssignID attachment is debug metadata, don't drop it.
1475   KnownSet.insert(LLVMContext::MD_DIAssignID);
1476
1477   auto &MetadataStore = getContext().pImpl->ValueMetadata;
1478   MDAttachments &Info = MetadataStore.find(this)->second;
1479   assert(!Info.empty() && "bit out of sync with hash table");
1480   Info.remove_if([&KnownSet](const MDAttachments::Attachment &I) {
1481     return !KnownSet.count(I.MDKind);
1482   });
1483
1484   if (Info.empty()) {
1485     // Drop our entry at the store.
1486     clearMetadata();
1487   }
1488 }
1489
1490 void Instruction::updateDIAssignIDMapping(DIAssignID *ID) {
1491   auto &IDToInstrs = getContext().pImpl->AssignmentIDToInstrs;
1492   if (const DIAssignID *CurrentID =
1493           cast_or_null<DIAssignID>(getMetadata(LLVMContext::MD_DIAssignID))) {
1494     // Nothing to do if the ID isn't changing.
1495     if (ID == CurrentID)
1496       return;
1497
1498     // Unmap this instruction from its current ID.
1499     auto InstrsIt = IDToInstrs.find(CurrentID);
1500     assert(InstrsIt != IDToInstrs.end() &&
1501            "Expect existing attachment to be mapped");
1502
1503     auto &InstVec = InstrsIt->second;
1504     auto *InstIt = std::find(InstVec.begin(), InstVec.end(), this);
1505     assert(InstIt != InstVec.end() &&
1506            "Expect instruction to be mapped to attachment");
1507     // The vector contains a ptr to this. If this is the only element in the
1508     // vector, remove the ID:vector entry, otherwise just remove the
1509     // instruction from the vector.
1510     if (InstVec.size() == 1)
1511       IDToInstrs.erase(InstrsIt);
1512     else
1513       InstVec.erase(InstIt);
1514   }
1515
1516   // Map this instruction to the new ID.
1517   if (ID)
1518     IDToInstrs[ID].push_back(this);
1519 }
1520
1521 void Instruction::setMetadata(unsigned KindID, MDNode *Node) {
1522   if (!Node && !hasMetadata())
1523     return;
1524
1525   // Handle 'dbg' as a special case since it is not stored in the hash table.
1526   if (KindID == LLVMContext::MD_dbg) {
1527     DbgLoc = DebugLoc(Node);
1528     return;
1529   }
1530
1531   // Update DIAssignID to Instruction(s) mapping.
1532   if (KindID == LLVMContext::MD_DIAssignID) {
1533     // The DIAssignID tracking infrastructure doesn't support RAUWing temporary
1534     // nodes with DIAssignIDs. The cast_or_null below would also catch this, but
1535     // having a dedicated assert helps make this obvious.
1536     assert((!Node || !Node->isTemporary()) &&
1537            "Temporary DIAssignIDs are invalid");
1538     updateDIAssignIDMapping(cast_or_null<DIAssignID>(Node));
1539   }
1540
1541   Value::setMetadata(KindID, Node);
1542 }
1543
1544 void Instruction::addAnnotationMetadata(SmallVector<StringRef> Annotations) {
1545   SmallSetVector<StringRef, 2> AnnotationsSet(Annotations.begin(),
1546                                               Annotations.end());
1547   MDBuilder MDB(getContext());
1548
1549   auto *Existing = getMetadata(LLVMContext::MD_annotation);
1550   SmallVector<Metadata *, 4> Names;
1551   if (Existing) {
1552     auto *Tuple = cast<MDTuple>(Existing);
1553     for (auto &N : Tuple->operands()) {
1554       if (isa<MDString>(N.get())) {
1555         Names.push_back(N);
1556         continue;
1557       }
1558       auto *MDAnnotationTuple = cast<MDTuple>(N);
1559       if (any_of(MDAnnotationTuple->operands(), [&AnnotationsSet](auto &Op) {
1560             return AnnotationsSet.contains(cast<MDString>(Op)->getString());
1561           }))
1562         return;
1563       Names.push_back(N);
1564     }
1565   }
1566
1567   SmallVector<Metadata *> MDAnnotationStrings;
1568   for (StringRef Annotation : Annotations)
1569     MDAnnotationStrings.push_back(MDB.createString(Annotation));
1570   MDNode *InfoTuple = MDTuple::get(getContext(), MDAnnotationStrings);
1571   Names.push_back(InfoTuple);
1572   MDNode *MD = MDTuple::get(getContext(), Names);
1573   setMetadata(LLVMContext::MD_annotation, MD);
1574 }
1575
1576 void Instruction::addAnnotationMetadata(StringRef Name) {
1577   MDBuilder MDB(getContext());
1578
1579   auto *Existing = getMetadata(LLVMContext::MD_annotation);
1580   SmallVector<Metadata *, 4> Names;
1581   if (Existing) {
1582     auto *Tuple = cast<MDTuple>(Existing);
1583     for (auto &N : Tuple->operands()) {
1584       if (isa<MDString>(N.get()) &&
1585           cast<MDString>(N.get())->getString() == Name)
1586         return;
1587       Names.push_back(N.get());
1588     }
1589   }
1590
1591   Names.push_back(MDB.createString(Name));
1592   MDNode *MD = MDTuple::get(getContext(), Names);
1593   setMetadata(LLVMContext::MD_annotation, MD);
1594 }
1595
1596 AAMDNodes Instruction::getAAMetadata() const {
1597   AAMDNodes Result;
1598   // Not using Instruction::hasMetadata() because we're not interested in
1599   // DebugInfoMetadata.
1600   if (Value::hasMetadata()) {
1601     const MDAttachments &Info = getContext().pImpl->ValueMetadata.at(this);
1602     Result.TBAA = Info.lookup(LLVMContext::MD_tbaa);
1603     Result.TBAAStruct = Info.lookup(LLVMContext::MD_tbaa_struct);
1604     Result.Scope = Info.lookup(LLVMContext::MD_alias_scope);
1605     Result.NoAlias = Info.lookup(LLVMContext::MD_noalias);
1606   }
1607   return Result;
1608 }
1609
1610 void Instruction::setAAMetadata(const AAMDNodes &N) {
1611   setMetadata(LLVMContext::MD_tbaa, N.TBAA);
1612   setMetadata(LLVMContext::MD_tbaa_struct, N.TBAAStruct);
1613   setMetadata(LLVMContext::MD_alias_scope, N.Scope);
1614   setMetadata(LLVMContext::MD_noalias, N.NoAlias);
1615 }
1616
1617 void Instruction::setNoSanitizeMetadata() {
1618   setMetadata(llvm::LLVMContext::MD_nosanitize,
1619               llvm::MDNode::get(getContext(), std::nullopt));
1620 }
1621
1622 void Instruction::getAllMetadataImpl(
1623     SmallVectorImpl<std::pair<unsigned, MDNode *>> &Result) const {
1624   Result.clear();
1625
1626   // Handle 'dbg' as a special case since it is not stored in the hash table.
1627   if (DbgLoc) {
1628     Result.push_back(
1629         std::make_pair((unsigned)LLVMContext::MD_dbg, DbgLoc.getAsMDNode()));
1630   }
1631   Value::getAllMetadata(Result);
1632 }
1633
1634 bool Instruction::extractProfTotalWeight(uint64_t &TotalVal) const {
1635   assert(
1636       (getOpcode() == Instruction::Br || getOpcode() == Instruction::Select ||
1637        getOpcode() == Instruction::Call || getOpcode() == Instruction::Invoke ||
1638        getOpcode() == Instruction::IndirectBr ||
1639        getOpcode() == Instruction::Switch) &&
1640       "Looking for branch weights on something besides branch");
1641
1642   return ::extractProfTotalWeight(*this, TotalVal);
1643 }
1644
1645 void GlobalObject::copyMetadata(const GlobalObject *Other, unsigned Offset) {
1646   SmallVector<std::pair<unsigned, MDNode *>, 8> MDs;
1647   Other->getAllMetadata(MDs);
1648   for (auto &MD : MDs) {
1649     // We need to adjust the type metadata offset.
1650     if (Offset != 0 && MD.first == LLVMContext::MD_type) {
1651       auto *OffsetConst = cast<ConstantInt>(
1652           cast<ConstantAsMetadata>(MD.second->getOperand(0))->getValue());
1653       Metadata *TypeId = MD.second->getOperand(1);
1654       auto *NewOffsetMD = ConstantAsMetadata::get(ConstantInt::get(
1655           OffsetConst->getType(), OffsetConst->getValue() + Offset));
1656       addMetadata(LLVMContext::MD_type,
1657                   *MDNode::get(getContext(), {NewOffsetMD, TypeId}));
1658       continue;
1659     }
1660     // If an offset adjustment was specified we need to modify the DIExpression
1661     // to prepend the adjustment:
1662     // !DIExpression(DW_OP_plus, Offset, [original expr])
1663     auto *Attachment = MD.second;
1664     if (Offset != 0 && MD.first == LLVMContext::MD_dbg) {
1665       DIGlobalVariable *GV = dyn_cast<DIGlobalVariable>(Attachment);
1666       DIExpression *E = nullptr;
1667       if (!GV) {
1668         auto *GVE = cast<DIGlobalVariableExpression>(Attachment);
1669         GV = GVE->getVariable();
1670         E = GVE->getExpression();
1671       }
1672       ArrayRef<uint64_t> OrigElements;
1673       if (E)
1674         OrigElements = E->getElements();
1675       std::vector<uint64_t> Elements(OrigElements.size() + 2);
1676       Elements[0] = dwarf::DW_OP_plus_uconst;
1677       Elements[1] = Offset;
1678       llvm::copy(OrigElements, Elements.begin() + 2);
1679       E = DIExpression::get(getContext(), Elements);
1680       Attachment = DIGlobalVariableExpression::get(getContext(), GV, E);
1681     }
1682     addMetadata(MD.first, *Attachment);
1683   }
1684 }
1685
1686 void GlobalObject::addTypeMetadata(unsigned Offset, Metadata *TypeID) {
1687   addMetadata(
1688       LLVMContext::MD_type,
1689       *MDTuple::get(getContext(),
1690                     {ConstantAsMetadata::get(ConstantInt::get(
1691                          Type::getInt64Ty(getContext()), Offset)),
1692                      TypeID}));
1693 }
1694
1695 void GlobalObject::setVCallVisibilityMetadata(VCallVisibility Visibility) {
1696   // Remove any existing vcall visibility metadata first in case we are
1697   // updating.
1698   eraseMetadata(LLVMContext::MD_vcall_visibility);
1699   addMetadata(LLVMContext::MD_vcall_visibility,
1700               *MDNode::get(getContext(),
1701                            {ConstantAsMetadata::get(ConstantInt::get(
1702                                Type::getInt64Ty(getContext()), Visibility))}));
1703 }
1704
1705 GlobalObject::VCallVisibility GlobalObject::getVCallVisibility() const {
1706   if (MDNode *MD = getMetadata(LLVMContext::MD_vcall_visibility)) {
1707     uint64_t Val = cast<ConstantInt>(
1708                        cast<ConstantAsMetadata>(MD->getOperand(0))->getValue())
1709                        ->getZExtValue();
1710     assert(Val <= 2 && "unknown vcall visibility!");
1711     return (VCallVisibility)Val;
1712   }
1713   return VCallVisibility::VCallVisibilityPublic;
1714 }
1715
1716 void Function::setSubprogram(DISubprogram *SP) {
1717   setMetadata(LLVMContext::MD_dbg, SP);
1718 }
1719
1720 DISubprogram *Function::getSubprogram() const {
1721   return cast_or_null<DISubprogram>(getMetadata(LLVMContext::MD_dbg));
1722 }
1723
1724 bool Function::shouldEmitDebugInfoForProfiling() const {
1725   if (DISubprogram *SP = getSubprogram()) {
1726     if (DICompileUnit *CU = SP->getUnit()) {
1727       return CU->getDebugInfoForProfiling();
1728     }
1729   }
1730   return false;
1731 }
1732
1733 void GlobalVariable::addDebugInfo(DIGlobalVariableExpression *GV) {
1734   addMetadata(LLVMContext::MD_dbg, *GV);
1735 }
1736
1737 void GlobalVariable::getDebugInfo(
1738     SmallVectorImpl<DIGlobalVariableExpression *> &GVs) const {
1739   SmallVector<MDNode *, 1> MDs;
1740   getMetadata(LLVMContext::MD_dbg, MDs);
1741   for (MDNode *MD : MDs)
1742     GVs.push_back(cast<DIGlobalVariableExpression>(MD));
1743 }