1288943Sdim//===- Metadata.cpp - Implement Metadata classes --------------------------===// 2249259Sdim// 3249259Sdim// The LLVM Compiler Infrastructure 4249259Sdim// 5249259Sdim// This file is distributed under the University of Illinois Open Source 6249259Sdim// License. See LICENSE.TXT for details. 7249259Sdim// 8249259Sdim//===----------------------------------------------------------------------===// 9249259Sdim// 10249259Sdim// This file implements the Metadata classes. 11249259Sdim// 12249259Sdim//===----------------------------------------------------------------------===// 13249259Sdim 14249259Sdim#include "llvm/IR/Metadata.h" 15249259Sdim#include "LLVMContextImpl.h" 16288943Sdim#include "MetadataImpl.h" 17249259Sdim#include "SymbolTableListTraitsImpl.h" 18249259Sdim#include "llvm/ADT/DenseMap.h" 19249259Sdim#include "llvm/ADT/STLExtras.h" 20276479Sdim#include "llvm/ADT/SmallSet.h" 21249259Sdim#include "llvm/ADT/SmallString.h" 22249259Sdim#include "llvm/ADT/StringMap.h" 23276479Sdim#include "llvm/IR/ConstantRange.h" 24288943Sdim#include "llvm/IR/DebugInfoMetadata.h" 25249259Sdim#include "llvm/IR/Instruction.h" 26249259Sdim#include "llvm/IR/LLVMContext.h" 27249259Sdim#include "llvm/IR/Module.h" 28276479Sdim#include "llvm/IR/ValueHandle.h" 29280031Sdim 30249259Sdimusing namespace llvm; 31249259Sdim 32280031SdimMetadataAsValue::MetadataAsValue(Type *Ty, Metadata *MD) 33280031Sdim : Value(Ty, MetadataAsValueVal), MD(MD) { 34280031Sdim track(); 35280031Sdim} 36249259Sdim 37280031SdimMetadataAsValue::~MetadataAsValue() { 38280031Sdim getType()->getContext().pImpl->MetadataAsValues.erase(MD); 39280031Sdim untrack(); 40280031Sdim} 41249259Sdim 42280031Sdim/// \brief Canonicalize metadata arguments to intrinsics. 43280031Sdim/// 44280031Sdim/// To support bitcode upgrades (and assembly semantic sugar) for \a 45280031Sdim/// MetadataAsValue, we need to canonicalize certain metadata. 46280031Sdim/// 47280031Sdim/// - nullptr is replaced by an empty MDNode. 48280031Sdim/// - An MDNode with a single null operand is replaced by an empty MDNode. 49280031Sdim/// - An MDNode whose only operand is a \a ConstantAsMetadata gets skipped. 50280031Sdim/// 51280031Sdim/// This maintains readability of bitcode from when metadata was a type of 52280031Sdim/// value, and these bridges were unnecessary. 53280031Sdimstatic Metadata *canonicalizeMetadataForValue(LLVMContext &Context, 54280031Sdim Metadata *MD) { 55280031Sdim if (!MD) 56280031Sdim // !{} 57280031Sdim return MDNode::get(Context, None); 58249259Sdim 59280031Sdim // Return early if this isn't a single-operand MDNode. 60280031Sdim auto *N = dyn_cast<MDNode>(MD); 61280031Sdim if (!N || N->getNumOperands() != 1) 62280031Sdim return MD; 63249259Sdim 64280031Sdim if (!N->getOperand(0)) 65280031Sdim // !{} 66280031Sdim return MDNode::get(Context, None); 67249259Sdim 68280031Sdim if (auto *C = dyn_cast<ConstantAsMetadata>(N->getOperand(0))) 69280031Sdim // Look through the MDNode. 70280031Sdim return C; 71249259Sdim 72280031Sdim return MD; 73280031Sdim} 74249259Sdim 75280031SdimMetadataAsValue *MetadataAsValue::get(LLVMContext &Context, Metadata *MD) { 76280031Sdim MD = canonicalizeMetadataForValue(Context, MD); 77280031Sdim auto *&Entry = Context.pImpl->MetadataAsValues[MD]; 78280031Sdim if (!Entry) 79280031Sdim Entry = new MetadataAsValue(Type::getMetadataTy(Context), MD); 80280031Sdim return Entry; 81280031Sdim} 82249259Sdim 83280031SdimMetadataAsValue *MetadataAsValue::getIfExists(LLVMContext &Context, 84280031Sdim Metadata *MD) { 85280031Sdim MD = canonicalizeMetadataForValue(Context, MD); 86280031Sdim auto &Store = Context.pImpl->MetadataAsValues; 87288943Sdim return Store.lookup(MD); 88280031Sdim} 89249259Sdim 90280031Sdimvoid MetadataAsValue::handleChangedMetadata(Metadata *MD) { 91280031Sdim LLVMContext &Context = getContext(); 92280031Sdim MD = canonicalizeMetadataForValue(Context, MD); 93280031Sdim auto &Store = Context.pImpl->MetadataAsValues; 94249259Sdim 95280031Sdim // Stop tracking the old metadata. 96280031Sdim Store.erase(this->MD); 97280031Sdim untrack(); 98280031Sdim this->MD = nullptr; 99249259Sdim 100280031Sdim // Start tracking MD, or RAUW if necessary. 101280031Sdim auto *&Entry = Store[MD]; 102280031Sdim if (Entry) { 103280031Sdim replaceAllUsesWith(Entry); 104280031Sdim delete this; 105280031Sdim return; 106280031Sdim } 107249259Sdim 108280031Sdim this->MD = MD; 109280031Sdim track(); 110280031Sdim Entry = this; 111280031Sdim} 112249259Sdim 113280031Sdimvoid MetadataAsValue::track() { 114280031Sdim if (MD) 115280031Sdim MetadataTracking::track(&MD, *MD, *this); 116249259Sdim} 117249259Sdim 118280031Sdimvoid MetadataAsValue::untrack() { 119280031Sdim if (MD) 120280031Sdim MetadataTracking::untrack(MD); 121249259Sdim} 122249259Sdim 123296417Sdimbool MetadataTracking::track(void *Ref, Metadata &MD, OwnerTy Owner) { 124296417Sdim assert(Ref && "Expected live reference"); 125296417Sdim assert((Owner || *static_cast<Metadata **>(Ref) == &MD) && 126296417Sdim "Reference without owner must be direct"); 127296417Sdim if (auto *R = ReplaceableMetadataImpl::get(MD)) { 128296417Sdim R->addRef(Ref, Owner); 129296417Sdim return true; 130296417Sdim } 131296417Sdim return false; 132296417Sdim} 133296417Sdim 134296417Sdimvoid MetadataTracking::untrack(void *Ref, Metadata &MD) { 135296417Sdim assert(Ref && "Expected live reference"); 136296417Sdim if (auto *R = ReplaceableMetadataImpl::get(MD)) 137296417Sdim R->dropRef(Ref); 138296417Sdim} 139296417Sdim 140296417Sdimbool MetadataTracking::retrack(void *Ref, Metadata &MD, void *New) { 141296417Sdim assert(Ref && "Expected live reference"); 142296417Sdim assert(New && "Expected live reference"); 143296417Sdim assert(Ref != New && "Expected change"); 144296417Sdim if (auto *R = ReplaceableMetadataImpl::get(MD)) { 145296417Sdim R->moveRef(Ref, New, MD); 146296417Sdim return true; 147296417Sdim } 148296417Sdim return false; 149296417Sdim} 150296417Sdim 151296417Sdimbool MetadataTracking::isReplaceable(const Metadata &MD) { 152296417Sdim return ReplaceableMetadataImpl::get(const_cast<Metadata &>(MD)); 153296417Sdim} 154296417Sdim 155280031Sdimvoid ReplaceableMetadataImpl::addRef(void *Ref, OwnerTy Owner) { 156280031Sdim bool WasInserted = 157280031Sdim UseMap.insert(std::make_pair(Ref, std::make_pair(Owner, NextIndex))) 158280031Sdim .second; 159280031Sdim (void)WasInserted; 160280031Sdim assert(WasInserted && "Expected to add a reference"); 161249259Sdim 162280031Sdim ++NextIndex; 163280031Sdim assert(NextIndex != 0 && "Unexpected overflow"); 164249259Sdim} 165249259Sdim 166280031Sdimvoid ReplaceableMetadataImpl::dropRef(void *Ref) { 167280031Sdim bool WasErased = UseMap.erase(Ref); 168280031Sdim (void)WasErased; 169280031Sdim assert(WasErased && "Expected to drop a reference"); 170249259Sdim} 171249259Sdim 172280031Sdimvoid ReplaceableMetadataImpl::moveRef(void *Ref, void *New, 173280031Sdim const Metadata &MD) { 174280031Sdim auto I = UseMap.find(Ref); 175280031Sdim assert(I != UseMap.end() && "Expected to move a reference"); 176280031Sdim auto OwnerAndIndex = I->second; 177280031Sdim UseMap.erase(I); 178280031Sdim bool WasInserted = UseMap.insert(std::make_pair(New, OwnerAndIndex)).second; 179280031Sdim (void)WasInserted; 180280031Sdim assert(WasInserted && "Expected to add a reference"); 181249259Sdim 182280031Sdim // Check that the references are direct if there's no owner. 183280031Sdim (void)MD; 184280031Sdim assert((OwnerAndIndex.first || *static_cast<Metadata **>(Ref) == &MD) && 185280031Sdim "Reference without owner must be direct"); 186280031Sdim assert((OwnerAndIndex.first || *static_cast<Metadata **>(New) == &MD) && 187280031Sdim "Reference without owner must be direct"); 188280031Sdim} 189249259Sdim 190280031Sdimvoid ReplaceableMetadataImpl::replaceAllUsesWith(Metadata *MD) { 191288943Sdim assert(!(MD && isa<MDNode>(MD) && cast<MDNode>(MD)->isTemporary()) && 192288943Sdim "Expected non-temp node"); 193296417Sdim assert(CanReplace && 194296417Sdim "Attempted to replace Metadata marked for no replacement"); 195249259Sdim 196280031Sdim if (UseMap.empty()) 197280031Sdim return; 198280031Sdim 199280031Sdim // Copy out uses since UseMap will get touched below. 200280031Sdim typedef std::pair<void *, std::pair<OwnerTy, uint64_t>> UseTy; 201280031Sdim SmallVector<UseTy, 8> Uses(UseMap.begin(), UseMap.end()); 202280031Sdim std::sort(Uses.begin(), Uses.end(), [](const UseTy &L, const UseTy &R) { 203280031Sdim return L.second.second < R.second.second; 204280031Sdim }); 205280031Sdim for (const auto &Pair : Uses) { 206280031Sdim // Check that this Ref hasn't disappeared after RAUW (when updating a 207280031Sdim // previous Ref). 208280031Sdim if (!UseMap.count(Pair.first)) 209280031Sdim continue; 210280031Sdim 211280031Sdim OwnerTy Owner = Pair.second.first; 212280031Sdim if (!Owner) { 213280031Sdim // Update unowned tracking references directly. 214280031Sdim Metadata *&Ref = *static_cast<Metadata **>(Pair.first); 215280031Sdim Ref = MD; 216280031Sdim if (MD) 217280031Sdim MetadataTracking::track(Ref); 218280031Sdim UseMap.erase(Pair.first); 219280031Sdim continue; 220280031Sdim } 221280031Sdim 222280031Sdim // Check for MetadataAsValue. 223280031Sdim if (Owner.is<MetadataAsValue *>()) { 224280031Sdim Owner.get<MetadataAsValue *>()->handleChangedMetadata(MD); 225280031Sdim continue; 226280031Sdim } 227280031Sdim 228280031Sdim // There's a Metadata owner -- dispatch. 229280031Sdim Metadata *OwnerMD = Owner.get<Metadata *>(); 230280031Sdim switch (OwnerMD->getMetadataID()) { 231280031Sdim#define HANDLE_METADATA_LEAF(CLASS) \ 232280031Sdim case Metadata::CLASS##Kind: \ 233280031Sdim cast<CLASS>(OwnerMD)->handleChangedOperand(Pair.first, MD); \ 234280031Sdim continue; 235280031Sdim#include "llvm/IR/Metadata.def" 236280031Sdim default: 237280031Sdim llvm_unreachable("Invalid metadata subclass"); 238280031Sdim } 239249259Sdim } 240280031Sdim assert(UseMap.empty() && "Expected all uses to be replaced"); 241249259Sdim} 242249259Sdim 243280031Sdimvoid ReplaceableMetadataImpl::resolveAllUses(bool ResolveUsers) { 244280031Sdim if (UseMap.empty()) 245280031Sdim return; 246280031Sdim 247280031Sdim if (!ResolveUsers) { 248280031Sdim UseMap.clear(); 249280031Sdim return; 250249259Sdim } 251249259Sdim 252280031Sdim // Copy out uses since UseMap could get touched below. 253280031Sdim typedef std::pair<void *, std::pair<OwnerTy, uint64_t>> UseTy; 254280031Sdim SmallVector<UseTy, 8> Uses(UseMap.begin(), UseMap.end()); 255280031Sdim std::sort(Uses.begin(), Uses.end(), [](const UseTy &L, const UseTy &R) { 256280031Sdim return L.second.second < R.second.second; 257280031Sdim }); 258280031Sdim UseMap.clear(); 259280031Sdim for (const auto &Pair : Uses) { 260280031Sdim auto Owner = Pair.second.first; 261280031Sdim if (!Owner) 262280031Sdim continue; 263280031Sdim if (Owner.is<MetadataAsValue *>()) 264280031Sdim continue; 265280031Sdim 266288943Sdim // Resolve MDNodes that point at this. 267288943Sdim auto *OwnerMD = dyn_cast<MDNode>(Owner.get<Metadata *>()); 268280031Sdim if (!OwnerMD) 269280031Sdim continue; 270280031Sdim if (OwnerMD->isResolved()) 271280031Sdim continue; 272280031Sdim OwnerMD->decrementUnresolvedOperandCount(); 273280031Sdim } 274249259Sdim} 275249259Sdim 276296417SdimReplaceableMetadataImpl *ReplaceableMetadataImpl::get(Metadata &MD) { 277296417Sdim if (auto *N = dyn_cast<MDNode>(&MD)) 278296417Sdim return N->Context.getReplaceableUses(); 279296417Sdim return dyn_cast<ValueAsMetadata>(&MD); 280296417Sdim} 281296417Sdim 282280031Sdimstatic Function *getLocalFunction(Value *V) { 283280031Sdim assert(V && "Expected value"); 284280031Sdim if (auto *A = dyn_cast<Argument>(V)) 285249259Sdim return A->getParent(); 286280031Sdim if (BasicBlock *BB = cast<Instruction>(V)->getParent()) 287249259Sdim return BB->getParent(); 288276479Sdim return nullptr; 289249259Sdim} 290249259Sdim 291280031SdimValueAsMetadata *ValueAsMetadata::get(Value *V) { 292280031Sdim assert(V && "Unexpected null Value"); 293249259Sdim 294280031Sdim auto &Context = V->getContext(); 295280031Sdim auto *&Entry = Context.pImpl->ValuesAsMetadata[V]; 296280031Sdim if (!Entry) { 297280031Sdim assert((isa<Constant>(V) || isa<Argument>(V) || isa<Instruction>(V)) && 298280031Sdim "Expected constant or function-local value"); 299288943Sdim assert(!V->IsUsedByMD && 300280031Sdim "Expected this to be the only metadata use"); 301288943Sdim V->IsUsedByMD = true; 302280031Sdim if (auto *C = dyn_cast<Constant>(V)) 303280031Sdim Entry = new ConstantAsMetadata(C); 304276479Sdim else 305280031Sdim Entry = new LocalAsMetadata(V); 306249259Sdim } 307280031Sdim 308280031Sdim return Entry; 309249259Sdim} 310249259Sdim 311280031SdimValueAsMetadata *ValueAsMetadata::getIfExists(Value *V) { 312280031Sdim assert(V && "Unexpected null Value"); 313280031Sdim return V->getContext().pImpl->ValuesAsMetadata.lookup(V); 314280031Sdim} 315280031Sdim 316280031Sdimvoid ValueAsMetadata::handleDeletion(Value *V) { 317280031Sdim assert(V && "Expected valid value"); 318280031Sdim 319280031Sdim auto &Store = V->getType()->getContext().pImpl->ValuesAsMetadata; 320280031Sdim auto I = Store.find(V); 321280031Sdim if (I == Store.end()) 322280031Sdim return; 323280031Sdim 324280031Sdim // Remove old entry from the map. 325280031Sdim ValueAsMetadata *MD = I->second; 326280031Sdim assert(MD && "Expected valid metadata"); 327280031Sdim assert(MD->getValue() == V && "Expected valid mapping"); 328280031Sdim Store.erase(I); 329280031Sdim 330280031Sdim // Delete the metadata. 331280031Sdim MD->replaceAllUsesWith(nullptr); 332280031Sdim delete MD; 333280031Sdim} 334280031Sdim 335280031Sdimvoid ValueAsMetadata::handleRAUW(Value *From, Value *To) { 336280031Sdim assert(From && "Expected valid value"); 337280031Sdim assert(To && "Expected valid value"); 338280031Sdim assert(From != To && "Expected changed value"); 339280031Sdim assert(From->getType() == To->getType() && "Unexpected type change"); 340280031Sdim 341280031Sdim LLVMContext &Context = From->getType()->getContext(); 342280031Sdim auto &Store = Context.pImpl->ValuesAsMetadata; 343280031Sdim auto I = Store.find(From); 344280031Sdim if (I == Store.end()) { 345288943Sdim assert(!From->IsUsedByMD && 346280031Sdim "Expected From not to be used by metadata"); 347280031Sdim return; 348280031Sdim } 349280031Sdim 350280031Sdim // Remove old entry from the map. 351288943Sdim assert(From->IsUsedByMD && 352280031Sdim "Expected From to be used by metadata"); 353288943Sdim From->IsUsedByMD = false; 354280031Sdim ValueAsMetadata *MD = I->second; 355280031Sdim assert(MD && "Expected valid metadata"); 356280031Sdim assert(MD->getValue() == From && "Expected valid mapping"); 357280031Sdim Store.erase(I); 358280031Sdim 359280031Sdim if (isa<LocalAsMetadata>(MD)) { 360280031Sdim if (auto *C = dyn_cast<Constant>(To)) { 361280031Sdim // Local became a constant. 362280031Sdim MD->replaceAllUsesWith(ConstantAsMetadata::get(C)); 363280031Sdim delete MD; 364280031Sdim return; 365280031Sdim } 366280031Sdim if (getLocalFunction(From) && getLocalFunction(To) && 367280031Sdim getLocalFunction(From) != getLocalFunction(To)) { 368280031Sdim // Function changed. 369280031Sdim MD->replaceAllUsesWith(nullptr); 370280031Sdim delete MD; 371280031Sdim return; 372280031Sdim } 373280031Sdim } else if (!isa<Constant>(To)) { 374280031Sdim // Changed to function-local value. 375280031Sdim MD->replaceAllUsesWith(nullptr); 376280031Sdim delete MD; 377280031Sdim return; 378280031Sdim } 379280031Sdim 380280031Sdim auto *&Entry = Store[To]; 381280031Sdim if (Entry) { 382280031Sdim // The target already exists. 383280031Sdim MD->replaceAllUsesWith(Entry); 384280031Sdim delete MD; 385280031Sdim return; 386280031Sdim } 387280031Sdim 388280031Sdim // Update MD in place (and update the map entry). 389288943Sdim assert(!To->IsUsedByMD && 390280031Sdim "Expected this to be the only metadata use"); 391288943Sdim To->IsUsedByMD = true; 392280031Sdim MD->V = To; 393280031Sdim Entry = MD; 394280031Sdim} 395280031Sdim 396280031Sdim//===----------------------------------------------------------------------===// 397280031Sdim// MDString implementation. 398280031Sdim// 399280031Sdim 400280031SdimMDString *MDString::get(LLVMContext &Context, StringRef Str) { 401280031Sdim auto &Store = Context.pImpl->MDStringCache; 402280031Sdim auto I = Store.find(Str); 403280031Sdim if (I != Store.end()) 404280031Sdim return &I->second; 405280031Sdim 406280031Sdim auto *Entry = 407280031Sdim StringMapEntry<MDString>::Create(Str, Store.getAllocator(), MDString()); 408280031Sdim bool WasInserted = Store.insert(Entry); 409280031Sdim (void)WasInserted; 410280031Sdim assert(WasInserted && "Expected entry to be inserted"); 411280031Sdim Entry->second.Entry = Entry; 412280031Sdim return &Entry->second; 413280031Sdim} 414280031Sdim 415280031SdimStringRef MDString::getString() const { 416280031Sdim assert(Entry && "Expected to find string map entry"); 417280031Sdim return Entry->first(); 418280031Sdim} 419280031Sdim 420280031Sdim//===----------------------------------------------------------------------===// 421280031Sdim// MDNode implementation. 422280031Sdim// 423280031Sdim 424288943Sdim// Assert that the MDNode types will not be unaligned by the objects 425288943Sdim// prepended to them. 426288943Sdim#define HANDLE_MDNODE_LEAF(CLASS) \ 427288943Sdim static_assert( \ 428288943Sdim llvm::AlignOf<uint64_t>::Alignment >= llvm::AlignOf<CLASS>::Alignment, \ 429288943Sdim "Alignment is insufficient after objects prepended to " #CLASS); 430288943Sdim#include "llvm/IR/Metadata.def" 431288943Sdim 432280031Sdimvoid *MDNode::operator new(size_t Size, unsigned NumOps) { 433288943Sdim size_t OpSize = NumOps * sizeof(MDOperand); 434288943Sdim // uint64_t is the most aligned type we need support (ensured by static_assert 435288943Sdim // above) 436288943Sdim OpSize = RoundUpToAlignment(OpSize, llvm::alignOf<uint64_t>()); 437288943Sdim void *Ptr = reinterpret_cast<char *>(::operator new(OpSize + Size)) + OpSize; 438280031Sdim MDOperand *O = static_cast<MDOperand *>(Ptr); 439288943Sdim for (MDOperand *E = O - NumOps; O != E; --O) 440288943Sdim (void)new (O - 1) MDOperand; 441288943Sdim return Ptr; 442280031Sdim} 443280031Sdim 444280031Sdimvoid MDNode::operator delete(void *Mem) { 445280031Sdim MDNode *N = static_cast<MDNode *>(Mem); 446288943Sdim size_t OpSize = N->NumOperands * sizeof(MDOperand); 447288943Sdim OpSize = RoundUpToAlignment(OpSize, llvm::alignOf<uint64_t>()); 448288943Sdim 449280031Sdim MDOperand *O = static_cast<MDOperand *>(Mem); 450280031Sdim for (MDOperand *E = O - N->NumOperands; O != E; --O) 451280031Sdim (O - 1)->~MDOperand(); 452288943Sdim ::operator delete(reinterpret_cast<char *>(Mem) - OpSize); 453280031Sdim} 454280031Sdim 455288943SdimMDNode::MDNode(LLVMContext &Context, unsigned ID, StorageType Storage, 456288943Sdim ArrayRef<Metadata *> Ops1, ArrayRef<Metadata *> Ops2) 457288943Sdim : Metadata(ID, Storage), NumOperands(Ops1.size() + Ops2.size()), 458288943Sdim NumUnresolved(0), Context(Context) { 459288943Sdim unsigned Op = 0; 460288943Sdim for (Metadata *MD : Ops1) 461288943Sdim setOperand(Op++, MD); 462288943Sdim for (Metadata *MD : Ops2) 463288943Sdim setOperand(Op++, MD); 464288943Sdim 465288943Sdim if (isDistinct()) 466288943Sdim return; 467288943Sdim 468288943Sdim if (isUniqued()) 469288943Sdim // Check whether any operands are unresolved, requiring re-uniquing. If 470288943Sdim // not, don't support RAUW. 471288943Sdim if (!countUnresolvedOperands()) 472288943Sdim return; 473288943Sdim 474288943Sdim this->Context.makeReplaceable(make_unique<ReplaceableMetadataImpl>(Context)); 475280031Sdim} 476280031Sdim 477288943SdimTempMDNode MDNode::clone() const { 478288943Sdim switch (getMetadataID()) { 479288943Sdim default: 480288943Sdim llvm_unreachable("Invalid MDNode subclass"); 481288943Sdim#define HANDLE_MDNODE_LEAF(CLASS) \ 482288943Sdim case CLASS##Kind: \ 483288943Sdim return cast<CLASS>(this)->cloneImpl(); 484288943Sdim#include "llvm/IR/Metadata.def" 485288943Sdim } 486280031Sdim} 487280031Sdim 488280031Sdimstatic bool isOperandUnresolved(Metadata *Op) { 489280031Sdim if (auto *N = dyn_cast_or_null<MDNode>(Op)) 490280031Sdim return !N->isResolved(); 491280031Sdim return false; 492280031Sdim} 493280031Sdim 494288943Sdimunsigned MDNode::countUnresolvedOperands() { 495288943Sdim assert(NumUnresolved == 0 && "Expected unresolved ops to be uncounted"); 496288943Sdim NumUnresolved = std::count_if(op_begin(), op_end(), isOperandUnresolved); 497288943Sdim return NumUnresolved; 498288943Sdim} 499280031Sdim 500288943Sdimvoid MDNode::makeUniqued() { 501288943Sdim assert(isTemporary() && "Expected this to be temporary"); 502288943Sdim assert(!isResolved() && "Expected this to be unresolved"); 503280031Sdim 504288943Sdim // Enable uniquing callbacks. 505288943Sdim for (auto &Op : mutable_operands()) 506288943Sdim Op.reset(Op.get(), this); 507280031Sdim 508288943Sdim // Make this 'uniqued'. 509288943Sdim Storage = Uniqued; 510288943Sdim if (!countUnresolvedOperands()) 511288943Sdim resolve(); 512288943Sdim 513288943Sdim assert(isUniqued() && "Expected this to be uniqued"); 514280031Sdim} 515280031Sdim 516288943Sdimvoid MDNode::makeDistinct() { 517288943Sdim assert(isTemporary() && "Expected this to be temporary"); 518280031Sdim assert(!isResolved() && "Expected this to be unresolved"); 519280031Sdim 520288943Sdim // Pretend to be uniqued, resolve the node, and then store in distinct table. 521288943Sdim Storage = Uniqued; 522288943Sdim resolve(); 523288943Sdim storeDistinctInContext(); 524288943Sdim 525288943Sdim assert(isDistinct() && "Expected this to be distinct"); 526288943Sdim assert(isResolved() && "Expected this to be resolved"); 527288943Sdim} 528288943Sdim 529288943Sdimvoid MDNode::resolve() { 530288943Sdim assert(isUniqued() && "Expected this to be uniqued"); 531288943Sdim assert(!isResolved() && "Expected this to be unresolved"); 532288943Sdim 533280031Sdim // Move the map, so that this immediately looks resolved. 534288943Sdim auto Uses = Context.takeReplaceableUses(); 535288943Sdim NumUnresolved = 0; 536280031Sdim assert(isResolved() && "Expected this to be resolved"); 537280031Sdim 538280031Sdim // Drop RAUW support. 539280031Sdim Uses->resolveAllUses(); 540280031Sdim} 541280031Sdim 542288943Sdimvoid MDNode::resolveAfterOperandChange(Metadata *Old, Metadata *New) { 543288943Sdim assert(NumUnresolved != 0 && "Expected unresolved operands"); 544280031Sdim 545280031Sdim // Check if an operand was resolved. 546280031Sdim if (!isOperandUnresolved(Old)) { 547280031Sdim if (isOperandUnresolved(New)) 548280031Sdim // An operand was un-resolved! 549288943Sdim ++NumUnresolved; 550280031Sdim } else if (!isOperandUnresolved(New)) 551280031Sdim decrementUnresolvedOperandCount(); 552280031Sdim} 553280031Sdim 554288943Sdimvoid MDNode::decrementUnresolvedOperandCount() { 555288943Sdim if (!--NumUnresolved) 556280031Sdim // Last unresolved operand has just been resolved. 557280031Sdim resolve(); 558280031Sdim} 559280031Sdim 560296417Sdimvoid MDNode::resolveRecursivelyImpl(bool AllowTemps) { 561280031Sdim if (isResolved()) 562280031Sdim return; 563280031Sdim 564280031Sdim // Resolve this node immediately. 565280031Sdim resolve(); 566280031Sdim 567280031Sdim // Resolve all operands. 568280031Sdim for (const auto &Op : operands()) { 569288943Sdim auto *N = dyn_cast_or_null<MDNode>(Op); 570288943Sdim if (!N) 571280031Sdim continue; 572288943Sdim 573296417Sdim if (N->isTemporary() && AllowTemps) 574296417Sdim continue; 575288943Sdim assert(!N->isTemporary() && 576280031Sdim "Expected all forward declarations to be resolved"); 577288943Sdim if (!N->isResolved()) 578288943Sdim N->resolveCycles(); 579280031Sdim } 580280031Sdim} 581280031Sdim 582288943Sdimstatic bool hasSelfReference(MDNode *N) { 583288943Sdim for (Metadata *MD : N->operands()) 584288943Sdim if (MD == N) 585288943Sdim return true; 586288943Sdim return false; 587288943Sdim} 588288943Sdim 589288943SdimMDNode *MDNode::replaceWithPermanentImpl() { 590296417Sdim switch (getMetadataID()) { 591296417Sdim default: 592296417Sdim // If this type isn't uniquable, replace with a distinct node. 593296417Sdim return replaceWithDistinctImpl(); 594296417Sdim 595296417Sdim#define HANDLE_MDNODE_LEAF_UNIQUABLE(CLASS) \ 596296417Sdim case CLASS##Kind: \ 597296417Sdim break; 598296417Sdim#include "llvm/IR/Metadata.def" 599296417Sdim } 600296417Sdim 601296417Sdim // Even if this type is uniquable, self-references have to be distinct. 602288943Sdim if (hasSelfReference(this)) 603288943Sdim return replaceWithDistinctImpl(); 604288943Sdim return replaceWithUniquedImpl(); 605288943Sdim} 606288943Sdim 607288943SdimMDNode *MDNode::replaceWithUniquedImpl() { 608288943Sdim // Try to uniquify in place. 609288943Sdim MDNode *UniquedNode = uniquify(); 610288943Sdim 611288943Sdim if (UniquedNode == this) { 612288943Sdim makeUniqued(); 613288943Sdim return this; 614280031Sdim } 615288943Sdim 616288943Sdim // Collision, so RAUW instead. 617288943Sdim replaceAllUsesWith(UniquedNode); 618288943Sdim deleteAsSubclass(); 619288943Sdim return UniquedNode; 620249259Sdim} 621249259Sdim 622288943SdimMDNode *MDNode::replaceWithDistinctImpl() { 623288943Sdim makeDistinct(); 624288943Sdim return this; 625288943Sdim} 626288943Sdim 627288943Sdimvoid MDTuple::recalculateHash() { 628288943Sdim setHash(MDTupleInfo::KeyTy::calculateHash(this)); 629288943Sdim} 630288943Sdim 631280031Sdimvoid MDNode::dropAllReferences() { 632280031Sdim for (unsigned I = 0, E = NumOperands; I != E; ++I) 633280031Sdim setOperand(I, nullptr); 634288943Sdim if (!isResolved()) { 635288943Sdim Context.getReplaceableUses()->resolveAllUses(/* ResolveUsers */ false); 636288943Sdim (void)Context.takeReplaceableUses(); 637288943Sdim } 638249259Sdim} 639249259Sdim 640288943Sdimvoid MDNode::handleChangedOperand(void *Ref, Metadata *New) { 641280031Sdim unsigned Op = static_cast<MDOperand *>(Ref) - op_begin(); 642280031Sdim assert(Op < getNumOperands() && "Expected valid operand"); 643249259Sdim 644288943Sdim if (!isUniqued()) { 645280031Sdim // This node is not uniqued. Just set the operand and be done with it. 646280031Sdim setOperand(Op, New); 647280031Sdim return; 648280031Sdim } 649249259Sdim 650280031Sdim // This node is uniqued. 651280031Sdim eraseFromStore(); 652249259Sdim 653280031Sdim Metadata *Old = getOperand(Op); 654280031Sdim setOperand(Op, New); 655280031Sdim 656280031Sdim // Drop uniquing for self-reference cycles. 657280031Sdim if (New == this) { 658280031Sdim if (!isResolved()) 659280031Sdim resolve(); 660288943Sdim storeDistinctInContext(); 661280031Sdim return; 662280031Sdim } 663280031Sdim 664280031Sdim // Re-unique the node. 665280031Sdim auto *Uniqued = uniquify(); 666280031Sdim if (Uniqued == this) { 667280031Sdim if (!isResolved()) 668280031Sdim resolveAfterOperandChange(Old, New); 669280031Sdim return; 670280031Sdim } 671280031Sdim 672280031Sdim // Collision. 673280031Sdim if (!isResolved()) { 674280031Sdim // Still unresolved, so RAUW. 675280031Sdim // 676280031Sdim // First, clear out all operands to prevent any recursion (similar to 677280031Sdim // dropAllReferences(), but we still need the use-list). 678280031Sdim for (unsigned O = 0, E = getNumOperands(); O != E; ++O) 679280031Sdim setOperand(O, nullptr); 680288943Sdim Context.getReplaceableUses()->replaceAllUsesWith(Uniqued); 681280031Sdim deleteAsSubclass(); 682280031Sdim return; 683280031Sdim } 684280031Sdim 685280031Sdim // Store in non-uniqued form if RAUW isn't possible. 686280031Sdim storeDistinctInContext(); 687280031Sdim} 688280031Sdim 689288943Sdimvoid MDNode::deleteAsSubclass() { 690280031Sdim switch (getMetadataID()) { 691280031Sdim default: 692288943Sdim llvm_unreachable("Invalid subclass of MDNode"); 693288943Sdim#define HANDLE_MDNODE_LEAF(CLASS) \ 694280031Sdim case CLASS##Kind: \ 695280031Sdim delete cast<CLASS>(this); \ 696249259Sdim break; 697280031Sdim#include "llvm/IR/Metadata.def" 698280031Sdim } 699280031Sdim} 700280031Sdim 701288943Sdimtemplate <class T, class InfoT> 702288943Sdimstatic T *uniquifyImpl(T *N, DenseSet<T *, InfoT> &Store) { 703288943Sdim if (T *U = getUniqued(Store, N)) 704288943Sdim return U; 705288943Sdim 706288943Sdim Store.insert(N); 707288943Sdim return N; 708288943Sdim} 709288943Sdim 710288943Sdimtemplate <class NodeTy> struct MDNode::HasCachedHash { 711288943Sdim typedef char Yes[1]; 712288943Sdim typedef char No[2]; 713288943Sdim template <class U, U Val> struct SFINAE {}; 714288943Sdim 715288943Sdim template <class U> 716288943Sdim static Yes &check(SFINAE<void (U::*)(unsigned), &U::setHash> *); 717288943Sdim template <class U> static No &check(...); 718288943Sdim 719288943Sdim static const bool value = sizeof(check<NodeTy>(nullptr)) == sizeof(Yes); 720288943Sdim}; 721288943Sdim 722288943SdimMDNode *MDNode::uniquify() { 723288943Sdim assert(!hasSelfReference(this) && "Cannot uniquify a self-referencing node"); 724288943Sdim 725288943Sdim // Try to insert into uniquing store. 726280031Sdim switch (getMetadataID()) { 727280031Sdim default: 728296417Sdim llvm_unreachable("Invalid or non-uniquable subclass of MDNode"); 729296417Sdim#define HANDLE_MDNODE_LEAF_UNIQUABLE(CLASS) \ 730288943Sdim case CLASS##Kind: { \ 731288943Sdim CLASS *SubclassThis = cast<CLASS>(this); \ 732288943Sdim std::integral_constant<bool, HasCachedHash<CLASS>::value> \ 733288943Sdim ShouldRecalculateHash; \ 734288943Sdim dispatchRecalculateHash(SubclassThis, ShouldRecalculateHash); \ 735288943Sdim return uniquifyImpl(SubclassThis, getContext().pImpl->CLASS##s); \ 736288943Sdim } 737280031Sdim#include "llvm/IR/Metadata.def" 738280031Sdim } 739280031Sdim} 740280031Sdim 741288943Sdimvoid MDNode::eraseFromStore() { 742280031Sdim switch (getMetadataID()) { 743280031Sdim default: 744296417Sdim llvm_unreachable("Invalid or non-uniquable subclass of MDNode"); 745296417Sdim#define HANDLE_MDNODE_LEAF_UNIQUABLE(CLASS) \ 746280031Sdim case CLASS##Kind: \ 747288943Sdim getContext().pImpl->CLASS##s.erase(cast<CLASS>(this)); \ 748249259Sdim break; 749280031Sdim#include "llvm/IR/Metadata.def" 750249259Sdim } 751280031Sdim} 752249259Sdim 753280031SdimMDTuple *MDTuple::getImpl(LLVMContext &Context, ArrayRef<Metadata *> MDs, 754288943Sdim StorageType Storage, bool ShouldCreate) { 755288943Sdim unsigned Hash = 0; 756288943Sdim if (Storage == Uniqued) { 757288943Sdim MDTupleInfo::KeyTy Key(MDs); 758288943Sdim if (auto *N = getUniqued(Context.pImpl->MDTuples, Key)) 759288943Sdim return N; 760288943Sdim if (!ShouldCreate) 761288943Sdim return nullptr; 762288943Sdim Hash = Key.getHash(); 763288943Sdim } else { 764288943Sdim assert(ShouldCreate && "Expected non-uniqued nodes to always be created"); 765280031Sdim } 766249259Sdim 767288943Sdim return storeImpl(new (MDs.size()) MDTuple(Context, Storage, Hash, MDs), 768288943Sdim Storage, Context.pImpl->MDTuples); 769249259Sdim} 770249259Sdim 771288943Sdimvoid MDNode::deleteTemporary(MDNode *N) { 772288943Sdim assert(N->isTemporary() && "Expected temporary node"); 773288943Sdim N->replaceAllUsesWith(nullptr); 774288943Sdim N->deleteAsSubclass(); 775249259Sdim} 776249259Sdim 777288943Sdimvoid MDNode::storeDistinctInContext() { 778288943Sdim assert(isResolved() && "Expected resolved nodes"); 779288943Sdim Storage = Distinct; 780249259Sdim 781288943Sdim // Reset the hash. 782288943Sdim switch (getMetadataID()) { 783288943Sdim default: 784288943Sdim llvm_unreachable("Invalid subclass of MDNode"); 785288943Sdim#define HANDLE_MDNODE_LEAF(CLASS) \ 786288943Sdim case CLASS##Kind: { \ 787288943Sdim std::integral_constant<bool, HasCachedHash<CLASS>::value> ShouldResetHash; \ 788288943Sdim dispatchResetHash(cast<CLASS>(this), ShouldResetHash); \ 789288943Sdim break; \ 790249259Sdim } 791288943Sdim#include "llvm/IR/Metadata.def" 792288943Sdim } 793249259Sdim 794280031Sdim getContext().pImpl->DistinctMDNodes.insert(this); 795280031Sdim} 796249259Sdim 797280031Sdimvoid MDNode::replaceOperandWith(unsigned I, Metadata *New) { 798280031Sdim if (getOperand(I) == New) 799249259Sdim return; 800249259Sdim 801288943Sdim if (!isUniqued()) { 802280031Sdim setOperand(I, New); 803249259Sdim return; 804249259Sdim } 805249259Sdim 806288943Sdim handleChangedOperand(mutable_begin() + I, New); 807280031Sdim} 808249259Sdim 809280031Sdimvoid MDNode::setOperand(unsigned I, Metadata *New) { 810280031Sdim assert(I < NumOperands); 811288943Sdim mutable_begin()[I].reset(New, isUniqued() ? this : nullptr); 812280031Sdim} 813280031Sdim 814280031Sdim/// \brief Get a node, or a self-reference that looks like it. 815280031Sdim/// 816280031Sdim/// Special handling for finding self-references, for use by \a 817280031Sdim/// MDNode::concatenate() and \a MDNode::intersect() to maintain behaviour from 818280031Sdim/// when self-referencing nodes were still uniqued. If the first operand has 819280031Sdim/// the same operands as \c Ops, return the first operand instead. 820280031Sdimstatic MDNode *getOrSelfReference(LLVMContext &Context, 821280031Sdim ArrayRef<Metadata *> Ops) { 822280031Sdim if (!Ops.empty()) 823280031Sdim if (MDNode *N = dyn_cast_or_null<MDNode>(Ops[0])) 824280031Sdim if (N->getNumOperands() == Ops.size() && N == N->getOperand(0)) { 825280031Sdim for (unsigned I = 1, E = Ops.size(); I != E; ++I) 826280031Sdim if (Ops[I] != N->getOperand(I)) 827280031Sdim return MDNode::get(Context, Ops); 828280031Sdim return N; 829280031Sdim } 830280031Sdim 831280031Sdim return MDNode::get(Context, Ops); 832280031Sdim} 833280031Sdim 834280031SdimMDNode *MDNode::concatenate(MDNode *A, MDNode *B) { 835280031Sdim if (!A) 836280031Sdim return B; 837280031Sdim if (!B) 838280031Sdim return A; 839280031Sdim 840288943Sdim SmallVector<Metadata *, 4> MDs; 841288943Sdim MDs.reserve(A->getNumOperands() + B->getNumOperands()); 842288943Sdim MDs.append(A->op_begin(), A->op_end()); 843288943Sdim MDs.append(B->op_begin(), B->op_end()); 844280031Sdim 845280031Sdim // FIXME: This preserves long-standing behaviour, but is it really the right 846280031Sdim // behaviour? Or was that an unintended side-effect of node uniquing? 847280031Sdim return getOrSelfReference(A->getContext(), MDs); 848280031Sdim} 849280031Sdim 850280031SdimMDNode *MDNode::intersect(MDNode *A, MDNode *B) { 851280031Sdim if (!A || !B) 852280031Sdim return nullptr; 853280031Sdim 854280031Sdim SmallVector<Metadata *, 4> MDs; 855288943Sdim for (Metadata *MD : A->operands()) 856288943Sdim if (std::find(B->op_begin(), B->op_end(), MD) != B->op_end()) 857288943Sdim MDs.push_back(MD); 858280031Sdim 859280031Sdim // FIXME: This preserves long-standing behaviour, but is it really the right 860280031Sdim // behaviour? Or was that an unintended side-effect of node uniquing? 861280031Sdim return getOrSelfReference(A->getContext(), MDs); 862249259Sdim} 863249259Sdim 864280031SdimMDNode *MDNode::getMostGenericAliasScope(MDNode *A, MDNode *B) { 865280031Sdim if (!A || !B) 866280031Sdim return nullptr; 867280031Sdim 868280031Sdim SmallVector<Metadata *, 4> MDs(B->op_begin(), B->op_end()); 869288943Sdim for (Metadata *MD : A->operands()) 870288943Sdim if (std::find(B->op_begin(), B->op_end(), MD) == B->op_end()) 871288943Sdim MDs.push_back(MD); 872280031Sdim 873280031Sdim // FIXME: This preserves long-standing behaviour, but is it really the right 874280031Sdim // behaviour? Or was that an unintended side-effect of node uniquing? 875280031Sdim return getOrSelfReference(A->getContext(), MDs); 876280031Sdim} 877280031Sdim 878249259SdimMDNode *MDNode::getMostGenericFPMath(MDNode *A, MDNode *B) { 879249259Sdim if (!A || !B) 880276479Sdim return nullptr; 881249259Sdim 882280031Sdim APFloat AVal = mdconst::extract<ConstantFP>(A->getOperand(0))->getValueAPF(); 883280031Sdim APFloat BVal = mdconst::extract<ConstantFP>(B->getOperand(0))->getValueAPF(); 884249259Sdim if (AVal.compare(BVal) == APFloat::cmpLessThan) 885249259Sdim return A; 886249259Sdim return B; 887249259Sdim} 888249259Sdim 889249259Sdimstatic bool isContiguous(const ConstantRange &A, const ConstantRange &B) { 890249259Sdim return A.getUpper() == B.getLower() || A.getLower() == B.getUpper(); 891249259Sdim} 892249259Sdim 893249259Sdimstatic bool canBeMerged(const ConstantRange &A, const ConstantRange &B) { 894249259Sdim return !A.intersectWith(B).isEmptySet() || isContiguous(A, B); 895249259Sdim} 896249259Sdim 897280031Sdimstatic bool tryMergeRange(SmallVectorImpl<ConstantInt *> &EndPoints, 898280031Sdim ConstantInt *Low, ConstantInt *High) { 899249259Sdim ConstantRange NewRange(Low->getValue(), High->getValue()); 900249259Sdim unsigned Size = EndPoints.size(); 901280031Sdim APInt LB = EndPoints[Size - 2]->getValue(); 902280031Sdim APInt LE = EndPoints[Size - 1]->getValue(); 903249259Sdim ConstantRange LastRange(LB, LE); 904249259Sdim if (canBeMerged(NewRange, LastRange)) { 905249259Sdim ConstantRange Union = LastRange.unionWith(NewRange); 906249259Sdim Type *Ty = High->getType(); 907280031Sdim EndPoints[Size - 2] = 908280031Sdim cast<ConstantInt>(ConstantInt::get(Ty, Union.getLower())); 909280031Sdim EndPoints[Size - 1] = 910280031Sdim cast<ConstantInt>(ConstantInt::get(Ty, Union.getUpper())); 911249259Sdim return true; 912249259Sdim } 913249259Sdim return false; 914249259Sdim} 915249259Sdim 916280031Sdimstatic void addRange(SmallVectorImpl<ConstantInt *> &EndPoints, 917280031Sdim ConstantInt *Low, ConstantInt *High) { 918249259Sdim if (!EndPoints.empty()) 919249259Sdim if (tryMergeRange(EndPoints, Low, High)) 920249259Sdim return; 921249259Sdim 922249259Sdim EndPoints.push_back(Low); 923249259Sdim EndPoints.push_back(High); 924249259Sdim} 925249259Sdim 926249259SdimMDNode *MDNode::getMostGenericRange(MDNode *A, MDNode *B) { 927249259Sdim // Given two ranges, we want to compute the union of the ranges. This 928249259Sdim // is slightly complitade by having to combine the intervals and merge 929249259Sdim // the ones that overlap. 930249259Sdim 931249259Sdim if (!A || !B) 932276479Sdim return nullptr; 933249259Sdim 934249259Sdim if (A == B) 935249259Sdim return A; 936249259Sdim 937249259Sdim // First, walk both lists in older of the lower boundary of each interval. 938249259Sdim // At each step, try to merge the new interval to the last one we adedd. 939280031Sdim SmallVector<ConstantInt *, 4> EndPoints; 940249259Sdim int AI = 0; 941249259Sdim int BI = 0; 942249259Sdim int AN = A->getNumOperands() / 2; 943249259Sdim int BN = B->getNumOperands() / 2; 944249259Sdim while (AI < AN && BI < BN) { 945280031Sdim ConstantInt *ALow = mdconst::extract<ConstantInt>(A->getOperand(2 * AI)); 946280031Sdim ConstantInt *BLow = mdconst::extract<ConstantInt>(B->getOperand(2 * BI)); 947249259Sdim 948249259Sdim if (ALow->getValue().slt(BLow->getValue())) { 949280031Sdim addRange(EndPoints, ALow, 950280031Sdim mdconst::extract<ConstantInt>(A->getOperand(2 * AI + 1))); 951249259Sdim ++AI; 952249259Sdim } else { 953280031Sdim addRange(EndPoints, BLow, 954280031Sdim mdconst::extract<ConstantInt>(B->getOperand(2 * BI + 1))); 955249259Sdim ++BI; 956249259Sdim } 957249259Sdim } 958249259Sdim while (AI < AN) { 959280031Sdim addRange(EndPoints, mdconst::extract<ConstantInt>(A->getOperand(2 * AI)), 960280031Sdim mdconst::extract<ConstantInt>(A->getOperand(2 * AI + 1))); 961249259Sdim ++AI; 962249259Sdim } 963249259Sdim while (BI < BN) { 964280031Sdim addRange(EndPoints, mdconst::extract<ConstantInt>(B->getOperand(2 * BI)), 965280031Sdim mdconst::extract<ConstantInt>(B->getOperand(2 * BI + 1))); 966249259Sdim ++BI; 967249259Sdim } 968249259Sdim 969249259Sdim // If we have more than 2 ranges (4 endpoints) we have to try to merge 970249259Sdim // the last and first ones. 971249259Sdim unsigned Size = EndPoints.size(); 972249259Sdim if (Size > 4) { 973280031Sdim ConstantInt *FB = EndPoints[0]; 974280031Sdim ConstantInt *FE = EndPoints[1]; 975249259Sdim if (tryMergeRange(EndPoints, FB, FE)) { 976249259Sdim for (unsigned i = 0; i < Size - 2; ++i) { 977249259Sdim EndPoints[i] = EndPoints[i + 2]; 978249259Sdim } 979249259Sdim EndPoints.resize(Size - 2); 980249259Sdim } 981249259Sdim } 982249259Sdim 983249259Sdim // If in the end we have a single range, it is possible that it is now the 984249259Sdim // full range. Just drop the metadata in that case. 985249259Sdim if (EndPoints.size() == 2) { 986280031Sdim ConstantRange Range(EndPoints[0]->getValue(), EndPoints[1]->getValue()); 987249259Sdim if (Range.isFullSet()) 988276479Sdim return nullptr; 989249259Sdim } 990249259Sdim 991280031Sdim SmallVector<Metadata *, 4> MDs; 992280031Sdim MDs.reserve(EndPoints.size()); 993280031Sdim for (auto *I : EndPoints) 994280031Sdim MDs.push_back(ConstantAsMetadata::get(I)); 995280031Sdim return MDNode::get(A->getContext(), MDs); 996249259Sdim} 997249259Sdim 998296417SdimMDNode *MDNode::getMostGenericAlignmentOrDereferenceable(MDNode *A, MDNode *B) { 999296417Sdim if (!A || !B) 1000296417Sdim return nullptr; 1001296417Sdim 1002296417Sdim ConstantInt *AVal = mdconst::extract<ConstantInt>(A->getOperand(0)); 1003296417Sdim ConstantInt *BVal = mdconst::extract<ConstantInt>(B->getOperand(0)); 1004296417Sdim if (AVal->getZExtValue() < BVal->getZExtValue()) 1005296417Sdim return A; 1006296417Sdim return B; 1007296417Sdim} 1008296417Sdim 1009249259Sdim//===----------------------------------------------------------------------===// 1010249259Sdim// NamedMDNode implementation. 1011249259Sdim// 1012249259Sdim 1013280031Sdimstatic SmallVector<TrackingMDRef, 4> &getNMDOps(void *Operands) { 1014280031Sdim return *(SmallVector<TrackingMDRef, 4> *)Operands; 1015249259Sdim} 1016249259Sdim 1017249259SdimNamedMDNode::NamedMDNode(const Twine &N) 1018280031Sdim : Name(N.str()), Parent(nullptr), 1019280031Sdim Operands(new SmallVector<TrackingMDRef, 4>()) {} 1020249259Sdim 1021249259SdimNamedMDNode::~NamedMDNode() { 1022249259Sdim dropAllReferences(); 1023249259Sdim delete &getNMDOps(Operands); 1024249259Sdim} 1025249259Sdim 1026249259Sdimunsigned NamedMDNode::getNumOperands() const { 1027249259Sdim return (unsigned)getNMDOps(Operands).size(); 1028249259Sdim} 1029249259Sdim 1030249259SdimMDNode *NamedMDNode::getOperand(unsigned i) const { 1031249259Sdim assert(i < getNumOperands() && "Invalid Operand number!"); 1032280031Sdim auto *N = getNMDOps(Operands)[i].get(); 1033280031Sdim return cast_or_null<MDNode>(N); 1034249259Sdim} 1035249259Sdim 1036280031Sdimvoid NamedMDNode::addOperand(MDNode *M) { getNMDOps(Operands).emplace_back(M); } 1037280031Sdim 1038280031Sdimvoid NamedMDNode::setOperand(unsigned I, MDNode *New) { 1039280031Sdim assert(I < getNumOperands() && "Invalid operand number"); 1040280031Sdim getNMDOps(Operands)[I].reset(New); 1041249259Sdim} 1042249259Sdim 1043249259Sdimvoid NamedMDNode::eraseFromParent() { 1044249259Sdim getParent()->eraseNamedMetadata(this); 1045249259Sdim} 1046249259Sdim 1047249259Sdimvoid NamedMDNode::dropAllReferences() { 1048249259Sdim getNMDOps(Operands).clear(); 1049249259Sdim} 1050249259Sdim 1051249259SdimStringRef NamedMDNode::getName() const { 1052249259Sdim return StringRef(Name); 1053249259Sdim} 1054249259Sdim 1055249259Sdim//===----------------------------------------------------------------------===// 1056249259Sdim// Instruction Metadata method implementations. 1057249259Sdim// 1058288943Sdimvoid MDAttachmentMap::set(unsigned ID, MDNode &MD) { 1059288943Sdim for (auto &I : Attachments) 1060288943Sdim if (I.first == ID) { 1061288943Sdim I.second.reset(&MD); 1062288943Sdim return; 1063288943Sdim } 1064288943Sdim Attachments.emplace_back(std::piecewise_construct, std::make_tuple(ID), 1065288943Sdim std::make_tuple(&MD)); 1066288943Sdim} 1067249259Sdim 1068288943Sdimvoid MDAttachmentMap::erase(unsigned ID) { 1069288943Sdim if (empty()) 1070288943Sdim return; 1071288943Sdim 1072288943Sdim // Common case is one/last value. 1073288943Sdim if (Attachments.back().first == ID) { 1074288943Sdim Attachments.pop_back(); 1075288943Sdim return; 1076288943Sdim } 1077288943Sdim 1078288943Sdim for (auto I = Attachments.begin(), E = std::prev(Attachments.end()); I != E; 1079288943Sdim ++I) 1080288943Sdim if (I->first == ID) { 1081288943Sdim *I = std::move(Attachments.back()); 1082288943Sdim Attachments.pop_back(); 1083288943Sdim return; 1084288943Sdim } 1085288943Sdim} 1086288943Sdim 1087288943SdimMDNode *MDAttachmentMap::lookup(unsigned ID) const { 1088288943Sdim for (const auto &I : Attachments) 1089288943Sdim if (I.first == ID) 1090288943Sdim return I.second; 1091288943Sdim return nullptr; 1092288943Sdim} 1093288943Sdim 1094288943Sdimvoid MDAttachmentMap::getAll( 1095288943Sdim SmallVectorImpl<std::pair<unsigned, MDNode *>> &Result) const { 1096288943Sdim Result.append(Attachments.begin(), Attachments.end()); 1097288943Sdim 1098288943Sdim // Sort the resulting array so it is stable. 1099288943Sdim if (Result.size() > 1) 1100288943Sdim array_pod_sort(Result.begin(), Result.end()); 1101288943Sdim} 1102288943Sdim 1103249259Sdimvoid Instruction::setMetadata(StringRef Kind, MDNode *Node) { 1104280031Sdim if (!Node && !hasMetadata()) 1105280031Sdim return; 1106249259Sdim setMetadata(getContext().getMDKindID(Kind), Node); 1107249259Sdim} 1108249259Sdim 1109249259SdimMDNode *Instruction::getMetadataImpl(StringRef Kind) const { 1110249259Sdim return getMetadataImpl(getContext().getMDKindID(Kind)); 1111249259Sdim} 1112249259Sdim 1113296417Sdimvoid Instruction::dropUnknownNonDebugMetadata(ArrayRef<unsigned> KnownIDs) { 1114276479Sdim SmallSet<unsigned, 5> KnownSet; 1115276479Sdim KnownSet.insert(KnownIDs.begin(), KnownIDs.end()); 1116276479Sdim 1117276479Sdim if (!hasMetadataHashEntry()) 1118276479Sdim return; // Nothing to remove! 1119276479Sdim 1120288943Sdim auto &InstructionMetadata = getContext().pImpl->InstructionMetadata; 1121276479Sdim 1122276479Sdim if (KnownSet.empty()) { 1123276479Sdim // Just drop our entry at the store. 1124288943Sdim InstructionMetadata.erase(this); 1125276479Sdim setHasMetadataHashEntry(false); 1126276479Sdim return; 1127276479Sdim } 1128276479Sdim 1129288943Sdim auto &Info = InstructionMetadata[this]; 1130288943Sdim Info.remove_if([&KnownSet](const std::pair<unsigned, TrackingMDNodeRef> &I) { 1131288943Sdim return !KnownSet.count(I.first); 1132288943Sdim }); 1133276479Sdim 1134288943Sdim if (Info.empty()) { 1135276479Sdim // Drop our entry at the store. 1136288943Sdim InstructionMetadata.erase(this); 1137276479Sdim setHasMetadataHashEntry(false); 1138276479Sdim } 1139276479Sdim} 1140276479Sdim 1141296417Sdim/// setMetadata - Set the metadata of the specified kind to the specified 1142249259Sdim/// node. This updates/replaces metadata if already present, or removes it if 1143249259Sdim/// Node is null. 1144249259Sdimvoid Instruction::setMetadata(unsigned KindID, MDNode *Node) { 1145280031Sdim if (!Node && !hasMetadata()) 1146280031Sdim return; 1147249259Sdim 1148249259Sdim // Handle 'dbg' as a special case since it is not stored in the hash table. 1149249259Sdim if (KindID == LLVMContext::MD_dbg) { 1150288943Sdim DbgLoc = DebugLoc(Node); 1151249259Sdim return; 1152249259Sdim } 1153249259Sdim 1154249259Sdim // Handle the case when we're adding/updating metadata on an instruction. 1155249259Sdim if (Node) { 1156288943Sdim auto &Info = getContext().pImpl->InstructionMetadata[this]; 1157249259Sdim assert(!Info.empty() == hasMetadataHashEntry() && 1158249259Sdim "HasMetadata bit is wonked"); 1159288943Sdim if (Info.empty()) 1160249259Sdim setHasMetadataHashEntry(true); 1161288943Sdim Info.set(KindID, *Node); 1162249259Sdim return; 1163249259Sdim } 1164249259Sdim 1165249259Sdim // Otherwise, we're removing metadata from an instruction. 1166249259Sdim assert((hasMetadataHashEntry() == 1167288943Sdim (getContext().pImpl->InstructionMetadata.count(this) > 0)) && 1168249259Sdim "HasMetadata bit out of date!"); 1169249259Sdim if (!hasMetadataHashEntry()) 1170249259Sdim return; // Nothing to remove! 1171288943Sdim auto &Info = getContext().pImpl->InstructionMetadata[this]; 1172249259Sdim 1173288943Sdim // Handle removal of an existing value. 1174288943Sdim Info.erase(KindID); 1175288943Sdim 1176288943Sdim if (!Info.empty()) 1177249259Sdim return; 1178249259Sdim 1179288943Sdim getContext().pImpl->InstructionMetadata.erase(this); 1180288943Sdim setHasMetadataHashEntry(false); 1181249259Sdim} 1182249259Sdim 1183280031Sdimvoid Instruction::setAAMetadata(const AAMDNodes &N) { 1184280031Sdim setMetadata(LLVMContext::MD_tbaa, N.TBAA); 1185280031Sdim setMetadata(LLVMContext::MD_alias_scope, N.Scope); 1186280031Sdim setMetadata(LLVMContext::MD_noalias, N.NoAlias); 1187280031Sdim} 1188280031Sdim 1189249259SdimMDNode *Instruction::getMetadataImpl(unsigned KindID) const { 1190249259Sdim // Handle 'dbg' as a special case since it is not stored in the hash table. 1191249259Sdim if (KindID == LLVMContext::MD_dbg) 1192280031Sdim return DbgLoc.getAsMDNode(); 1193280031Sdim 1194288943Sdim if (!hasMetadataHashEntry()) 1195288943Sdim return nullptr; 1196288943Sdim auto &Info = getContext().pImpl->InstructionMetadata[this]; 1197249259Sdim assert(!Info.empty() && "bit out of sync with hash table"); 1198249259Sdim 1199288943Sdim return Info.lookup(KindID); 1200249259Sdim} 1201249259Sdim 1202280031Sdimvoid Instruction::getAllMetadataImpl( 1203280031Sdim SmallVectorImpl<std::pair<unsigned, MDNode *>> &Result) const { 1204249259Sdim Result.clear(); 1205249259Sdim 1206249259Sdim // Handle 'dbg' as a special case since it is not stored in the hash table. 1207288943Sdim if (DbgLoc) { 1208280031Sdim Result.push_back( 1209280031Sdim std::make_pair((unsigned)LLVMContext::MD_dbg, DbgLoc.getAsMDNode())); 1210249259Sdim if (!hasMetadataHashEntry()) return; 1211249259Sdim } 1212288943Sdim 1213249259Sdim assert(hasMetadataHashEntry() && 1214288943Sdim getContext().pImpl->InstructionMetadata.count(this) && 1215249259Sdim "Shouldn't have called this"); 1216288943Sdim const auto &Info = getContext().pImpl->InstructionMetadata.find(this)->second; 1217249259Sdim assert(!Info.empty() && "Shouldn't have called this"); 1218288943Sdim Info.getAll(Result); 1219249259Sdim} 1220249259Sdim 1221280031Sdimvoid Instruction::getAllMetadataOtherThanDebugLocImpl( 1222280031Sdim SmallVectorImpl<std::pair<unsigned, MDNode *>> &Result) const { 1223249259Sdim Result.clear(); 1224249259Sdim assert(hasMetadataHashEntry() && 1225288943Sdim getContext().pImpl->InstructionMetadata.count(this) && 1226249259Sdim "Shouldn't have called this"); 1227288943Sdim const auto &Info = getContext().pImpl->InstructionMetadata.find(this)->second; 1228249259Sdim assert(!Info.empty() && "Shouldn't have called this"); 1229288943Sdim Info.getAll(Result); 1230249259Sdim} 1231249259Sdim 1232249259Sdim/// clearMetadataHashEntries - Clear all hashtable-based metadata from 1233249259Sdim/// this instruction. 1234249259Sdimvoid Instruction::clearMetadataHashEntries() { 1235249259Sdim assert(hasMetadataHashEntry() && "Caller should check"); 1236288943Sdim getContext().pImpl->InstructionMetadata.erase(this); 1237249259Sdim setHasMetadataHashEntry(false); 1238249259Sdim} 1239288943Sdim 1240288943SdimMDNode *Function::getMetadata(unsigned KindID) const { 1241288943Sdim if (!hasMetadata()) 1242288943Sdim return nullptr; 1243288943Sdim return getContext().pImpl->FunctionMetadata[this].lookup(KindID); 1244288943Sdim} 1245288943Sdim 1246288943SdimMDNode *Function::getMetadata(StringRef Kind) const { 1247288943Sdim if (!hasMetadata()) 1248288943Sdim return nullptr; 1249288943Sdim return getMetadata(getContext().getMDKindID(Kind)); 1250288943Sdim} 1251288943Sdim 1252288943Sdimvoid Function::setMetadata(unsigned KindID, MDNode *MD) { 1253288943Sdim if (MD) { 1254288943Sdim if (!hasMetadata()) 1255288943Sdim setHasMetadataHashEntry(true); 1256288943Sdim 1257288943Sdim getContext().pImpl->FunctionMetadata[this].set(KindID, *MD); 1258288943Sdim return; 1259288943Sdim } 1260288943Sdim 1261288943Sdim // Nothing to unset. 1262288943Sdim if (!hasMetadata()) 1263288943Sdim return; 1264288943Sdim 1265288943Sdim auto &Store = getContext().pImpl->FunctionMetadata[this]; 1266288943Sdim Store.erase(KindID); 1267288943Sdim if (Store.empty()) 1268288943Sdim clearMetadata(); 1269288943Sdim} 1270288943Sdim 1271288943Sdimvoid Function::setMetadata(StringRef Kind, MDNode *MD) { 1272288943Sdim if (!MD && !hasMetadata()) 1273288943Sdim return; 1274288943Sdim setMetadata(getContext().getMDKindID(Kind), MD); 1275288943Sdim} 1276288943Sdim 1277288943Sdimvoid Function::getAllMetadata( 1278288943Sdim SmallVectorImpl<std::pair<unsigned, MDNode *>> &MDs) const { 1279288943Sdim MDs.clear(); 1280288943Sdim 1281288943Sdim if (!hasMetadata()) 1282288943Sdim return; 1283288943Sdim 1284288943Sdim getContext().pImpl->FunctionMetadata[this].getAll(MDs); 1285288943Sdim} 1286288943Sdim 1287288943Sdimvoid Function::dropUnknownMetadata(ArrayRef<unsigned> KnownIDs) { 1288288943Sdim if (!hasMetadata()) 1289288943Sdim return; 1290288943Sdim if (KnownIDs.empty()) { 1291288943Sdim clearMetadata(); 1292288943Sdim return; 1293288943Sdim } 1294288943Sdim 1295288943Sdim SmallSet<unsigned, 5> KnownSet; 1296288943Sdim KnownSet.insert(KnownIDs.begin(), KnownIDs.end()); 1297288943Sdim 1298288943Sdim auto &Store = getContext().pImpl->FunctionMetadata[this]; 1299288943Sdim assert(!Store.empty()); 1300288943Sdim 1301288943Sdim Store.remove_if([&KnownSet](const std::pair<unsigned, TrackingMDNodeRef> &I) { 1302288943Sdim return !KnownSet.count(I.first); 1303288943Sdim }); 1304288943Sdim 1305288943Sdim if (Store.empty()) 1306288943Sdim clearMetadata(); 1307288943Sdim} 1308288943Sdim 1309288943Sdimvoid Function::clearMetadata() { 1310288943Sdim if (!hasMetadata()) 1311288943Sdim return; 1312288943Sdim getContext().pImpl->FunctionMetadata.erase(this); 1313288943Sdim setHasMetadataHashEntry(false); 1314288943Sdim} 1315296417Sdim 1316296417Sdimvoid Function::setSubprogram(DISubprogram *SP) { 1317296417Sdim setMetadata(LLVMContext::MD_dbg, SP); 1318296417Sdim} 1319296417Sdim 1320296417SdimDISubprogram *Function::getSubprogram() const { 1321296417Sdim return cast_or_null<DISubprogram>(getMetadata(LLVMContext::MD_dbg)); 1322296417Sdim} 1323