1 //===- Metadata.cpp - Implement Metadata classes --------------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file implements the Metadata classes. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/IR/Metadata.h" 15 #include "LLVMContextImpl.h" 16 #include "MetadataImpl.h" 17 #include "SymbolTableListTraitsImpl.h" 18 #include "llvm/ADT/DenseMap.h" 19 #include "llvm/ADT/STLExtras.h" 20 #include "llvm/ADT/SmallSet.h" 21 #include "llvm/ADT/SmallString.h" 22 #include "llvm/ADT/StringMap.h" 23 #include "llvm/IR/ConstantRange.h" 24 #include "llvm/IR/DebugInfoMetadata.h" 25 #include "llvm/IR/Instruction.h" 26 #include "llvm/IR/LLVMContext.h" 27 #include "llvm/IR/Module.h" 28 #include "llvm/IR/ValueHandle.h" 29 30 using namespace llvm; 31 32 MetadataAsValue::MetadataAsValue(Type *Ty, Metadata *MD) 33 : Value(Ty, MetadataAsValueVal), MD(MD) { 34 track(); 35 } 36 37 MetadataAsValue::~MetadataAsValue() { 38 getType()->getContext().pImpl->MetadataAsValues.erase(MD); 39 untrack(); 40 } 41 42 /// \brief Canonicalize metadata arguments to intrinsics. 43 /// 44 /// To support bitcode upgrades (and assembly semantic sugar) for \a 45 /// MetadataAsValue, we need to canonicalize certain metadata. 46 /// 47 /// - nullptr is replaced by an empty MDNode. 48 /// - An MDNode with a single null operand is replaced by an empty MDNode. 49 /// - An MDNode whose only operand is a \a ConstantAsMetadata gets skipped. 50 /// 51 /// This maintains readability of bitcode from when metadata was a type of 52 /// value, and these bridges were unnecessary. 53 static Metadata *canonicalizeMetadataForValue(LLVMContext &Context, 54 Metadata *MD) { 55 if (!MD) 56 // !{} 57 return MDNode::get(Context, None); 58 59 // Return early if this isn't a single-operand MDNode. 60 auto *N = dyn_cast<MDNode>(MD); 61 if (!N || N->getNumOperands() != 1) 62 return MD; 63 64 if (!N->getOperand(0)) 65 // !{} 66 return MDNode::get(Context, None); 67 68 if (auto *C = dyn_cast<ConstantAsMetadata>(N->getOperand(0))) 69 // Look through the MDNode. 70 return C; 71 72 return MD; 73 } 74 75 MetadataAsValue *MetadataAsValue::get(LLVMContext &Context, Metadata *MD) { 76 MD = canonicalizeMetadataForValue(Context, MD); 77 auto *&Entry = Context.pImpl->MetadataAsValues[MD]; 78 if (!Entry) 79 Entry = new MetadataAsValue(Type::getMetadataTy(Context), MD); 80 return Entry; 81 } 82 83 MetadataAsValue *MetadataAsValue::getIfExists(LLVMContext &Context, 84 Metadata *MD) { 85 MD = canonicalizeMetadataForValue(Context, MD); 86 auto &Store = Context.pImpl->MetadataAsValues; 87 return Store.lookup(MD); 88 } 89 90 void MetadataAsValue::handleChangedMetadata(Metadata *MD) { 91 LLVMContext &Context = getContext(); 92 MD = canonicalizeMetadataForValue(Context, MD); 93 auto &Store = Context.pImpl->MetadataAsValues; 94 95 // Stop tracking the old metadata. 96 Store.erase(this->MD); 97 untrack(); 98 this->MD = nullptr; 99 100 // Start tracking MD, or RAUW if necessary. 101 auto *&Entry = Store[MD]; 102 if (Entry) { 103 replaceAllUsesWith(Entry); 104 delete this; 105 return; 106 } 107 108 this->MD = MD; 109 track(); 110 Entry = this; 111 } 112 113 void MetadataAsValue::track() { 114 if (MD) 115 MetadataTracking::track(&MD, *MD, *this); 116 } 117 118 void MetadataAsValue::untrack() { 119 if (MD) 120 MetadataTracking::untrack(MD); 121 } 122 123 void ReplaceableMetadataImpl::addRef(void *Ref, OwnerTy Owner) { 124 bool WasInserted = 125 UseMap.insert(std::make_pair(Ref, std::make_pair(Owner, NextIndex))) 126 .second; 127 (void)WasInserted; 128 assert(WasInserted && "Expected to add a reference"); 129 130 ++NextIndex; 131 assert(NextIndex != 0 && "Unexpected overflow"); 132 } 133 134 void ReplaceableMetadataImpl::dropRef(void *Ref) { 135 bool WasErased = UseMap.erase(Ref); 136 (void)WasErased; 137 assert(WasErased && "Expected to drop a reference"); 138 } 139 140 void ReplaceableMetadataImpl::moveRef(void *Ref, void *New, 141 const Metadata &MD) { 142 auto I = UseMap.find(Ref); 143 assert(I != UseMap.end() && "Expected to move a reference"); 144 auto OwnerAndIndex = I->second; 145 UseMap.erase(I); 146 bool WasInserted = UseMap.insert(std::make_pair(New, OwnerAndIndex)).second; 147 (void)WasInserted; 148 assert(WasInserted && "Expected to add a reference"); 149 150 // Check that the references are direct if there's no owner. 151 (void)MD; 152 assert((OwnerAndIndex.first || *static_cast<Metadata **>(Ref) == &MD) && 153 "Reference without owner must be direct"); 154 assert((OwnerAndIndex.first || *static_cast<Metadata **>(New) == &MD) && 155 "Reference without owner must be direct"); 156 } 157 158 void ReplaceableMetadataImpl::replaceAllUsesWith(Metadata *MD) { 159 assert(!(MD && isa<MDNode>(MD) && cast<MDNode>(MD)->isTemporary()) && 160 "Expected non-temp node"); 161 162 if (UseMap.empty()) 163 return; 164 165 // Copy out uses since UseMap will get touched below. 166 typedef std::pair<void *, std::pair<OwnerTy, uint64_t>> UseTy; 167 SmallVector<UseTy, 8> Uses(UseMap.begin(), UseMap.end()); 168 std::sort(Uses.begin(), Uses.end(), [](const UseTy &L, const UseTy &R) { 169 return L.second.second < R.second.second; 170 }); 171 for (const auto &Pair : Uses) { 172 // Check that this Ref hasn't disappeared after RAUW (when updating a 173 // previous Ref). 174 if (!UseMap.count(Pair.first)) 175 continue; 176 177 OwnerTy Owner = Pair.second.first; 178 if (!Owner) { 179 // Update unowned tracking references directly. 180 Metadata *&Ref = *static_cast<Metadata **>(Pair.first); 181 Ref = MD; 182 if (MD) 183 MetadataTracking::track(Ref); 184 UseMap.erase(Pair.first); 185 continue; 186 } 187 188 // Check for MetadataAsValue. 189 if (Owner.is<MetadataAsValue *>()) { 190 Owner.get<MetadataAsValue *>()->handleChangedMetadata(MD); 191 continue; 192 } 193 194 // There's a Metadata owner -- dispatch. 195 Metadata *OwnerMD = Owner.get<Metadata *>(); 196 switch (OwnerMD->getMetadataID()) { 197 #define HANDLE_METADATA_LEAF(CLASS) \ 198 case Metadata::CLASS##Kind: \ 199 cast<CLASS>(OwnerMD)->handleChangedOperand(Pair.first, MD); \ 200 continue; 201 #include "llvm/IR/Metadata.def" 202 default: 203 llvm_unreachable("Invalid metadata subclass"); 204 } 205 } 206 assert(UseMap.empty() && "Expected all uses to be replaced"); 207 } 208 209 void ReplaceableMetadataImpl::resolveAllUses(bool ResolveUsers) { 210 if (UseMap.empty()) 211 return; 212 213 if (!ResolveUsers) { 214 UseMap.clear(); 215 return; 216 } 217 218 // Copy out uses since UseMap could get touched below. 219 typedef std::pair<void *, std::pair<OwnerTy, uint64_t>> UseTy; 220 SmallVector<UseTy, 8> Uses(UseMap.begin(), UseMap.end()); 221 std::sort(Uses.begin(), Uses.end(), [](const UseTy &L, const UseTy &R) { 222 return L.second.second < R.second.second; 223 }); 224 UseMap.clear(); 225 for (const auto &Pair : Uses) { 226 auto Owner = Pair.second.first; 227 if (!Owner) 228 continue; 229 if (Owner.is<MetadataAsValue *>()) 230 continue; 231 232 // Resolve MDNodes that point at this. 233 auto *OwnerMD = dyn_cast<MDNode>(Owner.get<Metadata *>()); 234 if (!OwnerMD) 235 continue; 236 if (OwnerMD->isResolved()) 237 continue; 238 OwnerMD->decrementUnresolvedOperandCount(); 239 } 240 } 241 242 static Function *getLocalFunction(Value *V) { 243 assert(V && "Expected value"); 244 if (auto *A = dyn_cast<Argument>(V)) 245 return A->getParent(); 246 if (BasicBlock *BB = cast<Instruction>(V)->getParent()) 247 return BB->getParent(); 248 return nullptr; 249 } 250 251 ValueAsMetadata *ValueAsMetadata::get(Value *V) { 252 assert(V && "Unexpected null Value"); 253 254 auto &Context = V->getContext(); 255 auto *&Entry = Context.pImpl->ValuesAsMetadata[V]; 256 if (!Entry) { 257 assert((isa<Constant>(V) || isa<Argument>(V) || isa<Instruction>(V)) && 258 "Expected constant or function-local value"); 259 assert(!V->NameAndIsUsedByMD.getInt() && 260 "Expected this to be the only metadata use"); 261 V->NameAndIsUsedByMD.setInt(true); 262 if (auto *C = dyn_cast<Constant>(V)) 263 Entry = new ConstantAsMetadata(C); 264 else 265 Entry = new LocalAsMetadata(V); 266 } 267 268 return Entry; 269 } 270 271 ValueAsMetadata *ValueAsMetadata::getIfExists(Value *V) { 272 assert(V && "Unexpected null Value"); 273 return V->getContext().pImpl->ValuesAsMetadata.lookup(V); 274 } 275 276 void ValueAsMetadata::handleDeletion(Value *V) { 277 assert(V && "Expected valid value"); 278 279 auto &Store = V->getType()->getContext().pImpl->ValuesAsMetadata; 280 auto I = Store.find(V); 281 if (I == Store.end()) 282 return; 283 284 // Remove old entry from the map. 285 ValueAsMetadata *MD = I->second; 286 assert(MD && "Expected valid metadata"); 287 assert(MD->getValue() == V && "Expected valid mapping"); 288 Store.erase(I); 289 290 // Delete the metadata. 291 MD->replaceAllUsesWith(nullptr); 292 delete MD; 293 } 294 295 void ValueAsMetadata::handleRAUW(Value *From, Value *To) { 296 assert(From && "Expected valid value"); 297 assert(To && "Expected valid value"); 298 assert(From != To && "Expected changed value"); 299 assert(From->getType() == To->getType() && "Unexpected type change"); 300 301 LLVMContext &Context = From->getType()->getContext(); 302 auto &Store = Context.pImpl->ValuesAsMetadata; 303 auto I = Store.find(From); 304 if (I == Store.end()) { 305 assert(!From->NameAndIsUsedByMD.getInt() && 306 "Expected From not to be used by metadata"); 307 return; 308 } 309 310 // Remove old entry from the map. 311 assert(From->NameAndIsUsedByMD.getInt() && 312 "Expected From to be used by metadata"); 313 From->NameAndIsUsedByMD.setInt(false); 314 ValueAsMetadata *MD = I->second; 315 assert(MD && "Expected valid metadata"); 316 assert(MD->getValue() == From && "Expected valid mapping"); 317 Store.erase(I); 318 319 if (isa<LocalAsMetadata>(MD)) { 320 if (auto *C = dyn_cast<Constant>(To)) { 321 // Local became a constant. 322 MD->replaceAllUsesWith(ConstantAsMetadata::get(C)); 323 delete MD; 324 return; 325 } 326 if (getLocalFunction(From) && getLocalFunction(To) && 327 getLocalFunction(From) != getLocalFunction(To)) { 328 // Function changed. 329 MD->replaceAllUsesWith(nullptr); 330 delete MD; 331 return; 332 } 333 } else if (!isa<Constant>(To)) { 334 // Changed to function-local value. 335 MD->replaceAllUsesWith(nullptr); 336 delete MD; 337 return; 338 } 339 340 auto *&Entry = Store[To]; 341 if (Entry) { 342 // The target already exists. 343 MD->replaceAllUsesWith(Entry); 344 delete MD; 345 return; 346 } 347 348 // Update MD in place (and update the map entry). 349 assert(!To->NameAndIsUsedByMD.getInt() && 350 "Expected this to be the only metadata use"); 351 To->NameAndIsUsedByMD.setInt(true); 352 MD->V = To; 353 Entry = MD; 354 } 355 356 //===----------------------------------------------------------------------===// 357 // MDString implementation. 358 // 359 360 MDString *MDString::get(LLVMContext &Context, StringRef Str) { 361 auto &Store = Context.pImpl->MDStringCache; 362 auto I = Store.find(Str); 363 if (I != Store.end()) 364 return &I->second; 365 366 auto *Entry = 367 StringMapEntry<MDString>::Create(Str, Store.getAllocator(), MDString()); 368 bool WasInserted = Store.insert(Entry); 369 (void)WasInserted; 370 assert(WasInserted && "Expected entry to be inserted"); 371 Entry->second.Entry = Entry; 372 return &Entry->second; 373 } 374 375 StringRef MDString::getString() const { 376 assert(Entry && "Expected to find string map entry"); 377 return Entry->first(); 378 } 379 380 //===----------------------------------------------------------------------===// 381 // MDNode implementation. 382 // 383 384 void *MDNode::operator new(size_t Size, unsigned NumOps) { 385 void *Ptr = ::operator new(Size + NumOps * sizeof(MDOperand)); 386 MDOperand *O = static_cast<MDOperand *>(Ptr); 387 for (MDOperand *E = O + NumOps; O != E; ++O) 388 (void)new (O) MDOperand; 389 return O; 390 } 391 392 void MDNode::operator delete(void *Mem) { 393 MDNode *N = static_cast<MDNode *>(Mem); 394 MDOperand *O = static_cast<MDOperand *>(Mem); 395 for (MDOperand *E = O - N->NumOperands; O != E; --O) 396 (O - 1)->~MDOperand(); 397 ::operator delete(O); 398 } 399 400 MDNode::MDNode(LLVMContext &Context, unsigned ID, StorageType Storage, 401 ArrayRef<Metadata *> Ops1, ArrayRef<Metadata *> Ops2) 402 : Metadata(ID, Storage), NumOperands(Ops1.size() + Ops2.size()), 403 NumUnresolved(0), Context(Context) { 404 unsigned Op = 0; 405 for (Metadata *MD : Ops1) 406 setOperand(Op++, MD); 407 for (Metadata *MD : Ops2) 408 setOperand(Op++, MD); 409 410 if (isDistinct()) 411 return; 412 413 if (isUniqued()) 414 // Check whether any operands are unresolved, requiring re-uniquing. If 415 // not, don't support RAUW. 416 if (!countUnresolvedOperands()) 417 return; 418 419 this->Context.makeReplaceable(make_unique<ReplaceableMetadataImpl>(Context)); 420 } 421 422 TempMDNode MDNode::clone() const { 423 switch (getMetadataID()) { 424 default: 425 llvm_unreachable("Invalid MDNode subclass"); 426 #define HANDLE_MDNODE_LEAF(CLASS) \ 427 case CLASS##Kind: \ 428 return cast<CLASS>(this)->cloneImpl(); 429 #include "llvm/IR/Metadata.def" 430 } 431 } 432 433 static bool isOperandUnresolved(Metadata *Op) { 434 if (auto *N = dyn_cast_or_null<MDNode>(Op)) 435 return !N->isResolved(); 436 return false; 437 } 438 439 unsigned MDNode::countUnresolvedOperands() { 440 assert(NumUnresolved == 0 && "Expected unresolved ops to be uncounted"); 441 NumUnresolved = std::count_if(op_begin(), op_end(), isOperandUnresolved); 442 return NumUnresolved; 443 } 444 445 void MDNode::makeUniqued() { 446 assert(isTemporary() && "Expected this to be temporary"); 447 assert(!isResolved() && "Expected this to be unresolved"); 448 449 // Enable uniquing callbacks. 450 for (auto &Op : mutable_operands()) 451 Op.reset(Op.get(), this); 452 453 // Make this 'uniqued'. 454 Storage = Uniqued; 455 if (!countUnresolvedOperands()) 456 resolve(); 457 458 assert(isUniqued() && "Expected this to be uniqued"); 459 } 460 461 void MDNode::makeDistinct() { 462 assert(isTemporary() && "Expected this to be temporary"); 463 assert(!isResolved() && "Expected this to be unresolved"); 464 465 // Pretend to be uniqued, resolve the node, and then store in distinct table. 466 Storage = Uniqued; 467 resolve(); 468 storeDistinctInContext(); 469 470 assert(isDistinct() && "Expected this to be distinct"); 471 assert(isResolved() && "Expected this to be resolved"); 472 } 473 474 void MDNode::resolve() { 475 assert(isUniqued() && "Expected this to be uniqued"); 476 assert(!isResolved() && "Expected this to be unresolved"); 477 478 // Move the map, so that this immediately looks resolved. 479 auto Uses = Context.takeReplaceableUses(); 480 NumUnresolved = 0; 481 assert(isResolved() && "Expected this to be resolved"); 482 483 // Drop RAUW support. 484 Uses->resolveAllUses(); 485 } 486 487 void MDNode::resolveAfterOperandChange(Metadata *Old, Metadata *New) { 488 assert(NumUnresolved != 0 && "Expected unresolved operands"); 489 490 // Check if an operand was resolved. 491 if (!isOperandUnresolved(Old)) { 492 if (isOperandUnresolved(New)) 493 // An operand was un-resolved! 494 ++NumUnresolved; 495 } else if (!isOperandUnresolved(New)) 496 decrementUnresolvedOperandCount(); 497 } 498 499 void MDNode::decrementUnresolvedOperandCount() { 500 if (!--NumUnresolved) 501 // Last unresolved operand has just been resolved. 502 resolve(); 503 } 504 505 void MDNode::resolveCycles() { 506 if (isResolved()) 507 return; 508 509 // Resolve this node immediately. 510 resolve(); 511 512 // Resolve all operands. 513 for (const auto &Op : operands()) { 514 auto *N = dyn_cast_or_null<MDNode>(Op); 515 if (!N) 516 continue; 517 518 assert(!N->isTemporary() && 519 "Expected all forward declarations to be resolved"); 520 if (!N->isResolved()) 521 N->resolveCycles(); 522 } 523 } 524 525 static bool hasSelfReference(MDNode *N) { 526 for (Metadata *MD : N->operands()) 527 if (MD == N) 528 return true; 529 return false; 530 } 531 532 MDNode *MDNode::replaceWithPermanentImpl() { 533 if (hasSelfReference(this)) 534 return replaceWithDistinctImpl(); 535 return replaceWithUniquedImpl(); 536 } 537 538 MDNode *MDNode::replaceWithUniquedImpl() { 539 // Try to uniquify in place. 540 MDNode *UniquedNode = uniquify(); 541 542 if (UniquedNode == this) { 543 makeUniqued(); 544 return this; 545 } 546 547 // Collision, so RAUW instead. 548 replaceAllUsesWith(UniquedNode); 549 deleteAsSubclass(); 550 return UniquedNode; 551 } 552 553 MDNode *MDNode::replaceWithDistinctImpl() { 554 makeDistinct(); 555 return this; 556 } 557 558 void MDTuple::recalculateHash() { 559 setHash(MDTupleInfo::KeyTy::calculateHash(this)); 560 } 561 562 void MDNode::dropAllReferences() { 563 for (unsigned I = 0, E = NumOperands; I != E; ++I) 564 setOperand(I, nullptr); 565 if (!isResolved()) { 566 Context.getReplaceableUses()->resolveAllUses(/* ResolveUsers */ false); 567 (void)Context.takeReplaceableUses(); 568 } 569 } 570 571 void MDNode::handleChangedOperand(void *Ref, Metadata *New) { 572 unsigned Op = static_cast<MDOperand *>(Ref) - op_begin(); 573 assert(Op < getNumOperands() && "Expected valid operand"); 574 575 if (!isUniqued()) { 576 // This node is not uniqued. Just set the operand and be done with it. 577 setOperand(Op, New); 578 return; 579 } 580 581 // This node is uniqued. 582 eraseFromStore(); 583 584 Metadata *Old = getOperand(Op); 585 setOperand(Op, New); 586 587 // Drop uniquing for self-reference cycles. 588 if (New == this) { 589 if (!isResolved()) 590 resolve(); 591 storeDistinctInContext(); 592 return; 593 } 594 595 // Re-unique the node. 596 auto *Uniqued = uniquify(); 597 if (Uniqued == this) { 598 if (!isResolved()) 599 resolveAfterOperandChange(Old, New); 600 return; 601 } 602 603 // Collision. 604 if (!isResolved()) { 605 // Still unresolved, so RAUW. 606 // 607 // First, clear out all operands to prevent any recursion (similar to 608 // dropAllReferences(), but we still need the use-list). 609 for (unsigned O = 0, E = getNumOperands(); O != E; ++O) 610 setOperand(O, nullptr); 611 Context.getReplaceableUses()->replaceAllUsesWith(Uniqued); 612 deleteAsSubclass(); 613 return; 614 } 615 616 // Store in non-uniqued form if RAUW isn't possible. 617 storeDistinctInContext(); 618 } 619 620 void MDNode::deleteAsSubclass() { 621 switch (getMetadataID()) { 622 default: 623 llvm_unreachable("Invalid subclass of MDNode"); 624 #define HANDLE_MDNODE_LEAF(CLASS) \ 625 case CLASS##Kind: \ 626 delete cast<CLASS>(this); \ 627 break; 628 #include "llvm/IR/Metadata.def" 629 } 630 } 631 632 template <class T, class InfoT> 633 static T *uniquifyImpl(T *N, DenseSet<T *, InfoT> &Store) { 634 if (T *U = getUniqued(Store, N)) 635 return U; 636 637 Store.insert(N); 638 return N; 639 } 640 641 template <class NodeTy> struct MDNode::HasCachedHash { 642 typedef char Yes[1]; 643 typedef char No[2]; 644 template <class U, U Val> struct SFINAE {}; 645 646 template <class U> 647 static Yes &check(SFINAE<void (U::*)(unsigned), &U::setHash> *); 648 template <class U> static No &check(...); 649 650 static const bool value = sizeof(check<NodeTy>(nullptr)) == sizeof(Yes); 651 }; 652 653 MDNode *MDNode::uniquify() { 654 assert(!hasSelfReference(this) && "Cannot uniquify a self-referencing node"); 655 656 // Try to insert into uniquing store. 657 switch (getMetadataID()) { 658 default: 659 llvm_unreachable("Invalid subclass of MDNode"); 660 #define HANDLE_MDNODE_LEAF(CLASS) \ 661 case CLASS##Kind: { \ 662 CLASS *SubclassThis = cast<CLASS>(this); \ 663 std::integral_constant<bool, HasCachedHash<CLASS>::value> \ 664 ShouldRecalculateHash; \ 665 dispatchRecalculateHash(SubclassThis, ShouldRecalculateHash); \ 666 return uniquifyImpl(SubclassThis, getContext().pImpl->CLASS##s); \ 667 } 668 #include "llvm/IR/Metadata.def" 669 } 670 } 671 672 void MDNode::eraseFromStore() { 673 switch (getMetadataID()) { 674 default: 675 llvm_unreachable("Invalid subclass of MDNode"); 676 #define HANDLE_MDNODE_LEAF(CLASS) \ 677 case CLASS##Kind: \ 678 getContext().pImpl->CLASS##s.erase(cast<CLASS>(this)); \ 679 break; 680 #include "llvm/IR/Metadata.def" 681 } 682 } 683 684 MDTuple *MDTuple::getImpl(LLVMContext &Context, ArrayRef<Metadata *> MDs, 685 StorageType Storage, bool ShouldCreate) { 686 unsigned Hash = 0; 687 if (Storage == Uniqued) { 688 MDTupleInfo::KeyTy Key(MDs); 689 if (auto *N = getUniqued(Context.pImpl->MDTuples, Key)) 690 return N; 691 if (!ShouldCreate) 692 return nullptr; 693 Hash = Key.getHash(); 694 } else { 695 assert(ShouldCreate && "Expected non-uniqued nodes to always be created"); 696 } 697 698 return storeImpl(new (MDs.size()) MDTuple(Context, Storage, Hash, MDs), 699 Storage, Context.pImpl->MDTuples); 700 } 701 702 void MDNode::deleteTemporary(MDNode *N) { 703 assert(N->isTemporary() && "Expected temporary node"); 704 N->replaceAllUsesWith(nullptr); 705 N->deleteAsSubclass(); 706 } 707 708 void MDNode::storeDistinctInContext() { 709 assert(isResolved() && "Expected resolved nodes"); 710 Storage = Distinct; 711 712 // Reset the hash. 713 switch (getMetadataID()) { 714 default: 715 llvm_unreachable("Invalid subclass of MDNode"); 716 #define HANDLE_MDNODE_LEAF(CLASS) \ 717 case CLASS##Kind: { \ 718 std::integral_constant<bool, HasCachedHash<CLASS>::value> ShouldResetHash; \ 719 dispatchResetHash(cast<CLASS>(this), ShouldResetHash); \ 720 break; \ 721 } 722 #include "llvm/IR/Metadata.def" 723 } 724 725 getContext().pImpl->DistinctMDNodes.insert(this); 726 } 727 728 void MDNode::replaceOperandWith(unsigned I, Metadata *New) { 729 if (getOperand(I) == New) 730 return; 731 732 if (!isUniqued()) { 733 setOperand(I, New); 734 return; 735 } 736 737 handleChangedOperand(mutable_begin() + I, New); 738 } 739 740 void MDNode::setOperand(unsigned I, Metadata *New) { 741 assert(I < NumOperands); 742 mutable_begin()[I].reset(New, isUniqued() ? this : nullptr); 743 } 744 745 /// \brief Get a node, or a self-reference that looks like it. 746 /// 747 /// Special handling for finding self-references, for use by \a 748 /// MDNode::concatenate() and \a MDNode::intersect() to maintain behaviour from 749 /// when self-referencing nodes were still uniqued. If the first operand has 750 /// the same operands as \c Ops, return the first operand instead. 751 static MDNode *getOrSelfReference(LLVMContext &Context, 752 ArrayRef<Metadata *> Ops) { 753 if (!Ops.empty()) 754 if (MDNode *N = dyn_cast_or_null<MDNode>(Ops[0])) 755 if (N->getNumOperands() == Ops.size() && N == N->getOperand(0)) { 756 for (unsigned I = 1, E = Ops.size(); I != E; ++I) 757 if (Ops[I] != N->getOperand(I)) 758 return MDNode::get(Context, Ops); 759 return N; 760 } 761 762 return MDNode::get(Context, Ops); 763 } 764 765 MDNode *MDNode::concatenate(MDNode *A, MDNode *B) { 766 if (!A) 767 return B; 768 if (!B) 769 return A; 770 771 SmallVector<Metadata *, 4> MDs; 772 MDs.reserve(A->getNumOperands() + B->getNumOperands()); 773 MDs.append(A->op_begin(), A->op_end()); 774 MDs.append(B->op_begin(), B->op_end()); 775 776 // FIXME: This preserves long-standing behaviour, but is it really the right 777 // behaviour? Or was that an unintended side-effect of node uniquing? 778 return getOrSelfReference(A->getContext(), MDs); 779 } 780 781 MDNode *MDNode::intersect(MDNode *A, MDNode *B) { 782 if (!A || !B) 783 return nullptr; 784 785 SmallVector<Metadata *, 4> MDs; 786 for (Metadata *MD : A->operands()) 787 if (std::find(B->op_begin(), B->op_end(), MD) != B->op_end()) 788 MDs.push_back(MD); 789 790 // FIXME: This preserves long-standing behaviour, but is it really the right 791 // behaviour? Or was that an unintended side-effect of node uniquing? 792 return getOrSelfReference(A->getContext(), MDs); 793 } 794 795 MDNode *MDNode::getMostGenericAliasScope(MDNode *A, MDNode *B) { 796 if (!A || !B) 797 return nullptr; 798 799 SmallVector<Metadata *, 4> MDs(B->op_begin(), B->op_end()); 800 for (Metadata *MD : A->operands()) 801 if (std::find(B->op_begin(), B->op_end(), MD) == B->op_end()) 802 MDs.push_back(MD); 803 804 // FIXME: This preserves long-standing behaviour, but is it really the right 805 // behaviour? Or was that an unintended side-effect of node uniquing? 806 return getOrSelfReference(A->getContext(), MDs); 807 } 808 809 MDNode *MDNode::getMostGenericFPMath(MDNode *A, MDNode *B) { 810 if (!A || !B) 811 return nullptr; 812 813 APFloat AVal = mdconst::extract<ConstantFP>(A->getOperand(0))->getValueAPF(); 814 APFloat BVal = mdconst::extract<ConstantFP>(B->getOperand(0))->getValueAPF(); 815 if (AVal.compare(BVal) == APFloat::cmpLessThan) 816 return A; 817 return B; 818 } 819 820 static bool isContiguous(const ConstantRange &A, const ConstantRange &B) { 821 return A.getUpper() == B.getLower() || A.getLower() == B.getUpper(); 822 } 823 824 static bool canBeMerged(const ConstantRange &A, const ConstantRange &B) { 825 return !A.intersectWith(B).isEmptySet() || isContiguous(A, B); 826 } 827 828 static bool tryMergeRange(SmallVectorImpl<ConstantInt *> &EndPoints, 829 ConstantInt *Low, ConstantInt *High) { 830 ConstantRange NewRange(Low->getValue(), High->getValue()); 831 unsigned Size = EndPoints.size(); 832 APInt LB = EndPoints[Size - 2]->getValue(); 833 APInt LE = EndPoints[Size - 1]->getValue(); 834 ConstantRange LastRange(LB, LE); 835 if (canBeMerged(NewRange, LastRange)) { 836 ConstantRange Union = LastRange.unionWith(NewRange); 837 Type *Ty = High->getType(); 838 EndPoints[Size - 2] = 839 cast<ConstantInt>(ConstantInt::get(Ty, Union.getLower())); 840 EndPoints[Size - 1] = 841 cast<ConstantInt>(ConstantInt::get(Ty, Union.getUpper())); 842 return true; 843 } 844 return false; 845 } 846 847 static void addRange(SmallVectorImpl<ConstantInt *> &EndPoints, 848 ConstantInt *Low, ConstantInt *High) { 849 if (!EndPoints.empty()) 850 if (tryMergeRange(EndPoints, Low, High)) 851 return; 852 853 EndPoints.push_back(Low); 854 EndPoints.push_back(High); 855 } 856 857 MDNode *MDNode::getMostGenericRange(MDNode *A, MDNode *B) { 858 // Given two ranges, we want to compute the union of the ranges. This 859 // is slightly complitade by having to combine the intervals and merge 860 // the ones that overlap. 861 862 if (!A || !B) 863 return nullptr; 864 865 if (A == B) 866 return A; 867 868 // First, walk both lists in older of the lower boundary of each interval. 869 // At each step, try to merge the new interval to the last one we adedd. 870 SmallVector<ConstantInt *, 4> EndPoints; 871 int AI = 0; 872 int BI = 0; 873 int AN = A->getNumOperands() / 2; 874 int BN = B->getNumOperands() / 2; 875 while (AI < AN && BI < BN) { 876 ConstantInt *ALow = mdconst::extract<ConstantInt>(A->getOperand(2 * AI)); 877 ConstantInt *BLow = mdconst::extract<ConstantInt>(B->getOperand(2 * BI)); 878 879 if (ALow->getValue().slt(BLow->getValue())) { 880 addRange(EndPoints, ALow, 881 mdconst::extract<ConstantInt>(A->getOperand(2 * AI + 1))); 882 ++AI; 883 } else { 884 addRange(EndPoints, BLow, 885 mdconst::extract<ConstantInt>(B->getOperand(2 * BI + 1))); 886 ++BI; 887 } 888 } 889 while (AI < AN) { 890 addRange(EndPoints, mdconst::extract<ConstantInt>(A->getOperand(2 * AI)), 891 mdconst::extract<ConstantInt>(A->getOperand(2 * AI + 1))); 892 ++AI; 893 } 894 while (BI < BN) { 895 addRange(EndPoints, mdconst::extract<ConstantInt>(B->getOperand(2 * BI)), 896 mdconst::extract<ConstantInt>(B->getOperand(2 * BI + 1))); 897 ++BI; 898 } 899 900 // If we have more than 2 ranges (4 endpoints) we have to try to merge 901 // the last and first ones. 902 unsigned Size = EndPoints.size(); 903 if (Size > 4) { 904 ConstantInt *FB = EndPoints[0]; 905 ConstantInt *FE = EndPoints[1]; 906 if (tryMergeRange(EndPoints, FB, FE)) { 907 for (unsigned i = 0; i < Size - 2; ++i) { 908 EndPoints[i] = EndPoints[i + 2]; 909 } 910 EndPoints.resize(Size - 2); 911 } 912 } 913 914 // If in the end we have a single range, it is possible that it is now the 915 // full range. Just drop the metadata in that case. 916 if (EndPoints.size() == 2) { 917 ConstantRange Range(EndPoints[0]->getValue(), EndPoints[1]->getValue()); 918 if (Range.isFullSet()) 919 return nullptr; 920 } 921 922 SmallVector<Metadata *, 4> MDs; 923 MDs.reserve(EndPoints.size()); 924 for (auto *I : EndPoints) 925 MDs.push_back(ConstantAsMetadata::get(I)); 926 return MDNode::get(A->getContext(), MDs); 927 } 928 929 //===----------------------------------------------------------------------===// 930 // NamedMDNode implementation. 931 // 932 933 static SmallVector<TrackingMDRef, 4> &getNMDOps(void *Operands) { 934 return *(SmallVector<TrackingMDRef, 4> *)Operands; 935 } 936 937 NamedMDNode::NamedMDNode(const Twine &N) 938 : Name(N.str()), Parent(nullptr), 939 Operands(new SmallVector<TrackingMDRef, 4>()) {} 940 941 NamedMDNode::~NamedMDNode() { 942 dropAllReferences(); 943 delete &getNMDOps(Operands); 944 } 945 946 unsigned NamedMDNode::getNumOperands() const { 947 return (unsigned)getNMDOps(Operands).size(); 948 } 949 950 MDNode *NamedMDNode::getOperand(unsigned i) const { 951 assert(i < getNumOperands() && "Invalid Operand number!"); 952 auto *N = getNMDOps(Operands)[i].get(); 953 return cast_or_null<MDNode>(N); 954 } 955 956 void NamedMDNode::addOperand(MDNode *M) { getNMDOps(Operands).emplace_back(M); } 957 958 void NamedMDNode::setOperand(unsigned I, MDNode *New) { 959 assert(I < getNumOperands() && "Invalid operand number"); 960 getNMDOps(Operands)[I].reset(New); 961 } 962 963 void NamedMDNode::eraseFromParent() { 964 getParent()->eraseNamedMetadata(this); 965 } 966 967 void NamedMDNode::dropAllReferences() { 968 getNMDOps(Operands).clear(); 969 } 970 971 StringRef NamedMDNode::getName() const { 972 return StringRef(Name); 973 } 974 975 //===----------------------------------------------------------------------===// 976 // Instruction Metadata method implementations. 977 // 978 979 void Instruction::setMetadata(StringRef Kind, MDNode *Node) { 980 if (!Node && !hasMetadata()) 981 return; 982 setMetadata(getContext().getMDKindID(Kind), Node); 983 } 984 985 MDNode *Instruction::getMetadataImpl(StringRef Kind) const { 986 return getMetadataImpl(getContext().getMDKindID(Kind)); 987 } 988 989 void Instruction::dropUnknownMetadata(ArrayRef<unsigned> KnownIDs) { 990 SmallSet<unsigned, 5> KnownSet; 991 KnownSet.insert(KnownIDs.begin(), KnownIDs.end()); 992 993 // Drop debug if needed 994 if (KnownSet.erase(LLVMContext::MD_dbg)) 995 DbgLoc = DebugLoc(); 996 997 if (!hasMetadataHashEntry()) 998 return; // Nothing to remove! 999 1000 DenseMap<const Instruction *, LLVMContextImpl::MDMapTy> &MetadataStore = 1001 getContext().pImpl->MetadataStore; 1002 1003 if (KnownSet.empty()) { 1004 // Just drop our entry at the store. 1005 MetadataStore.erase(this); 1006 setHasMetadataHashEntry(false); 1007 return; 1008 } 1009 1010 LLVMContextImpl::MDMapTy &Info = MetadataStore[this]; 1011 unsigned I; 1012 unsigned E; 1013 // Walk the array and drop any metadata we don't know. 1014 for (I = 0, E = Info.size(); I != E;) { 1015 if (KnownSet.count(Info[I].first)) { 1016 ++I; 1017 continue; 1018 } 1019 1020 Info[I] = std::move(Info.back()); 1021 Info.pop_back(); 1022 --E; 1023 } 1024 assert(E == Info.size()); 1025 1026 if (E == 0) { 1027 // Drop our entry at the store. 1028 MetadataStore.erase(this); 1029 setHasMetadataHashEntry(false); 1030 } 1031 } 1032 1033 /// setMetadata - Set the metadata of of the specified kind to the specified 1034 /// node. This updates/replaces metadata if already present, or removes it if 1035 /// Node is null. 1036 void Instruction::setMetadata(unsigned KindID, MDNode *Node) { 1037 if (!Node && !hasMetadata()) 1038 return; 1039 1040 // Handle 'dbg' as a special case since it is not stored in the hash table. 1041 if (KindID == LLVMContext::MD_dbg) { 1042 DbgLoc = DebugLoc(Node); 1043 return; 1044 } 1045 1046 // Handle the case when we're adding/updating metadata on an instruction. 1047 if (Node) { 1048 LLVMContextImpl::MDMapTy &Info = getContext().pImpl->MetadataStore[this]; 1049 assert(!Info.empty() == hasMetadataHashEntry() && 1050 "HasMetadata bit is wonked"); 1051 if (Info.empty()) { 1052 setHasMetadataHashEntry(true); 1053 } else { 1054 // Handle replacement of an existing value. 1055 for (auto &P : Info) 1056 if (P.first == KindID) { 1057 P.second.reset(Node); 1058 return; 1059 } 1060 } 1061 1062 // No replacement, just add it to the list. 1063 Info.emplace_back(std::piecewise_construct, std::make_tuple(KindID), 1064 std::make_tuple(Node)); 1065 return; 1066 } 1067 1068 // Otherwise, we're removing metadata from an instruction. 1069 assert((hasMetadataHashEntry() == 1070 (getContext().pImpl->MetadataStore.count(this) > 0)) && 1071 "HasMetadata bit out of date!"); 1072 if (!hasMetadataHashEntry()) 1073 return; // Nothing to remove! 1074 LLVMContextImpl::MDMapTy &Info = getContext().pImpl->MetadataStore[this]; 1075 1076 // Common case is removing the only entry. 1077 if (Info.size() == 1 && Info[0].first == KindID) { 1078 getContext().pImpl->MetadataStore.erase(this); 1079 setHasMetadataHashEntry(false); 1080 return; 1081 } 1082 1083 // Handle removal of an existing value. 1084 for (unsigned i = 0, e = Info.size(); i != e; ++i) 1085 if (Info[i].first == KindID) { 1086 Info[i] = std::move(Info.back()); 1087 Info.pop_back(); 1088 assert(!Info.empty() && "Removing last entry should be handled above"); 1089 return; 1090 } 1091 // Otherwise, removing an entry that doesn't exist on the instruction. 1092 } 1093 1094 void Instruction::setAAMetadata(const AAMDNodes &N) { 1095 setMetadata(LLVMContext::MD_tbaa, N.TBAA); 1096 setMetadata(LLVMContext::MD_alias_scope, N.Scope); 1097 setMetadata(LLVMContext::MD_noalias, N.NoAlias); 1098 } 1099 1100 MDNode *Instruction::getMetadataImpl(unsigned KindID) const { 1101 // Handle 'dbg' as a special case since it is not stored in the hash table. 1102 if (KindID == LLVMContext::MD_dbg) 1103 return DbgLoc.getAsMDNode(); 1104 1105 if (!hasMetadataHashEntry()) return nullptr; 1106 1107 LLVMContextImpl::MDMapTy &Info = getContext().pImpl->MetadataStore[this]; 1108 assert(!Info.empty() && "bit out of sync with hash table"); 1109 1110 for (const auto &I : Info) 1111 if (I.first == KindID) 1112 return I.second; 1113 return nullptr; 1114 } 1115 1116 void Instruction::getAllMetadataImpl( 1117 SmallVectorImpl<std::pair<unsigned, MDNode *>> &Result) const { 1118 Result.clear(); 1119 1120 // Handle 'dbg' as a special case since it is not stored in the hash table. 1121 if (DbgLoc) { 1122 Result.push_back( 1123 std::make_pair((unsigned)LLVMContext::MD_dbg, DbgLoc.getAsMDNode())); 1124 if (!hasMetadataHashEntry()) return; 1125 } 1126 1127 assert(hasMetadataHashEntry() && 1128 getContext().pImpl->MetadataStore.count(this) && 1129 "Shouldn't have called this"); 1130 const LLVMContextImpl::MDMapTy &Info = 1131 getContext().pImpl->MetadataStore.find(this)->second; 1132 assert(!Info.empty() && "Shouldn't have called this"); 1133 1134 Result.reserve(Result.size() + Info.size()); 1135 for (auto &I : Info) 1136 Result.push_back(std::make_pair(I.first, cast<MDNode>(I.second.get()))); 1137 1138 // Sort the resulting array so it is stable. 1139 if (Result.size() > 1) 1140 array_pod_sort(Result.begin(), Result.end()); 1141 } 1142 1143 void Instruction::getAllMetadataOtherThanDebugLocImpl( 1144 SmallVectorImpl<std::pair<unsigned, MDNode *>> &Result) const { 1145 Result.clear(); 1146 assert(hasMetadataHashEntry() && 1147 getContext().pImpl->MetadataStore.count(this) && 1148 "Shouldn't have called this"); 1149 const LLVMContextImpl::MDMapTy &Info = 1150 getContext().pImpl->MetadataStore.find(this)->second; 1151 assert(!Info.empty() && "Shouldn't have called this"); 1152 Result.reserve(Result.size() + Info.size()); 1153 for (auto &I : Info) 1154 Result.push_back(std::make_pair(I.first, cast<MDNode>(I.second.get()))); 1155 1156 // Sort the resulting array so it is stable. 1157 if (Result.size() > 1) 1158 array_pod_sort(Result.begin(), Result.end()); 1159 } 1160 1161 /// clearMetadataHashEntries - Clear all hashtable-based metadata from 1162 /// this instruction. 1163 void Instruction::clearMetadataHashEntries() { 1164 assert(hasMetadataHashEntry() && "Caller should check"); 1165 getContext().pImpl->MetadataStore.erase(this); 1166 setHasMetadataHashEntry(false); 1167 } 1168