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