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