X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FIR%2FMetadata.cpp;h=752c4b276b710cb6f191b21204e3a116857a3e1b;hb=9cd7a4b72d2844550108d3da0b94b525428124fa;hp=3a7c293bcdd9b3794ea47d697465257f9707d04f;hpb=397b575f817010a9169b14cfbd8653493cd8ce3e;p=oota-llvm.git diff --git a/lib/IR/Metadata.cpp b/lib/IR/Metadata.cpp index 3a7c293bcdd..752c4b276b7 100644 --- a/lib/IR/Metadata.cpp +++ b/lib/IR/Metadata.cpp @@ -1,4 +1,4 @@ -//===-- Metadata.cpp - Implement Metadata classes -------------------------===// +//===- Metadata.cpp - Implement Metadata classes --------------------------===// // // The LLVM Compiler Infrastructure // @@ -13,6 +13,7 @@ #include "llvm/IR/Metadata.h" #include "LLVMContextImpl.h" +#include "MetadataImpl.h" #include "SymbolTableListTraitsImpl.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/STLExtras.h" @@ -20,23 +21,342 @@ #include "llvm/ADT/SmallString.h" #include "llvm/ADT/StringMap.h" #include "llvm/IR/ConstantRange.h" +#include "llvm/IR/DebugInfoMetadata.h" #include "llvm/IR/Instruction.h" #include "llvm/IR/LLVMContext.h" -#include "llvm/IR/LeakDetector.h" #include "llvm/IR/Module.h" #include "llvm/IR/ValueHandle.h" using namespace llvm; -Metadata::Metadata(LLVMContext &Context, unsigned ID) - : Value(Type::getMetadataTy(Context), ID) {} +MetadataAsValue::MetadataAsValue(Type *Ty, Metadata *MD) + : Value(Ty, MetadataAsValueVal), MD(MD) { + track(); +} + +MetadataAsValue::~MetadataAsValue() { + getType()->getContext().pImpl->MetadataAsValues.erase(MD); + untrack(); +} + +/// \brief Canonicalize metadata arguments to intrinsics. +/// +/// To support bitcode upgrades (and assembly semantic sugar) for \a +/// MetadataAsValue, we need to canonicalize certain metadata. +/// +/// - nullptr is replaced by an empty MDNode. +/// - An MDNode with a single null operand is replaced by an empty MDNode. +/// - An MDNode whose only operand is a \a ConstantAsMetadata gets skipped. +/// +/// This maintains readability of bitcode from when metadata was a type of +/// value, and these bridges were unnecessary. +static Metadata *canonicalizeMetadataForValue(LLVMContext &Context, + Metadata *MD) { + if (!MD) + // !{} + return MDNode::get(Context, None); + + // Return early if this isn't a single-operand MDNode. + auto *N = dyn_cast(MD); + if (!N || N->getNumOperands() != 1) + return MD; + + if (!N->getOperand(0)) + // !{} + return MDNode::get(Context, None); + + if (auto *C = dyn_cast(N->getOperand(0))) + // Look through the MDNode. + return C; + + return MD; +} + +MetadataAsValue *MetadataAsValue::get(LLVMContext &Context, Metadata *MD) { + MD = canonicalizeMetadataForValue(Context, MD); + auto *&Entry = Context.pImpl->MetadataAsValues[MD]; + if (!Entry) + Entry = new MetadataAsValue(Type::getMetadataTy(Context), MD); + return Entry; +} + +MetadataAsValue *MetadataAsValue::getIfExists(LLVMContext &Context, + Metadata *MD) { + MD = canonicalizeMetadataForValue(Context, MD); + auto &Store = Context.pImpl->MetadataAsValues; + return Store.lookup(MD); +} + +void MetadataAsValue::handleChangedMetadata(Metadata *MD) { + LLVMContext &Context = getContext(); + MD = canonicalizeMetadataForValue(Context, MD); + auto &Store = Context.pImpl->MetadataAsValues; + + // Stop tracking the old metadata. + Store.erase(this->MD); + untrack(); + this->MD = nullptr; + + // Start tracking MD, or RAUW if necessary. + auto *&Entry = Store[MD]; + if (Entry) { + replaceAllUsesWith(Entry); + delete this; + return; + } + + this->MD = MD; + track(); + Entry = this; +} + +void MetadataAsValue::track() { + if (MD) + MetadataTracking::track(&MD, *MD, *this); +} + +void MetadataAsValue::untrack() { + if (MD) + MetadataTracking::untrack(MD); +} + +void ReplaceableMetadataImpl::addRef(void *Ref, OwnerTy Owner) { + bool WasInserted = + UseMap.insert(std::make_pair(Ref, std::make_pair(Owner, NextIndex))) + .second; + (void)WasInserted; + assert(WasInserted && "Expected to add a reference"); + + ++NextIndex; + assert(NextIndex != 0 && "Unexpected overflow"); +} + +void ReplaceableMetadataImpl::dropRef(void *Ref) { + bool WasErased = UseMap.erase(Ref); + (void)WasErased; + assert(WasErased && "Expected to drop a reference"); +} + +void ReplaceableMetadataImpl::moveRef(void *Ref, void *New, + const Metadata &MD) { + auto I = UseMap.find(Ref); + assert(I != UseMap.end() && "Expected to move a reference"); + auto OwnerAndIndex = I->second; + UseMap.erase(I); + bool WasInserted = UseMap.insert(std::make_pair(New, OwnerAndIndex)).second; + (void)WasInserted; + assert(WasInserted && "Expected to add a reference"); + + // Check that the references are direct if there's no owner. + (void)MD; + assert((OwnerAndIndex.first || *static_cast(Ref) == &MD) && + "Reference without owner must be direct"); + assert((OwnerAndIndex.first || *static_cast(New) == &MD) && + "Reference without owner must be direct"); +} + +void ReplaceableMetadataImpl::replaceAllUsesWith(Metadata *MD) { + assert(!(MD && isa(MD) && cast(MD)->isTemporary()) && + "Expected non-temp node"); + + if (UseMap.empty()) + return; + + // Copy out uses since UseMap will get touched below. + typedef std::pair> UseTy; + SmallVector Uses(UseMap.begin(), UseMap.end()); + std::sort(Uses.begin(), Uses.end(), [](const UseTy &L, const UseTy &R) { + return L.second.second < R.second.second; + }); + for (const auto &Pair : Uses) { + // Check that this Ref hasn't disappeared after RAUW (when updating a + // previous Ref). + if (!UseMap.count(Pair.first)) + continue; + + OwnerTy Owner = Pair.second.first; + if (!Owner) { + // Update unowned tracking references directly. + Metadata *&Ref = *static_cast(Pair.first); + Ref = MD; + if (MD) + MetadataTracking::track(Ref); + UseMap.erase(Pair.first); + continue; + } + + // Check for MetadataAsValue. + if (Owner.is()) { + Owner.get()->handleChangedMetadata(MD); + continue; + } + + // There's a Metadata owner -- dispatch. + Metadata *OwnerMD = Owner.get(); + switch (OwnerMD->getMetadataID()) { +#define HANDLE_METADATA_LEAF(CLASS) \ + case Metadata::CLASS##Kind: \ + cast(OwnerMD)->handleChangedOperand(Pair.first, MD); \ + continue; +#include "llvm/IR/Metadata.def" + default: + llvm_unreachable("Invalid metadata subclass"); + } + } + assert(UseMap.empty() && "Expected all uses to be replaced"); +} + +void ReplaceableMetadataImpl::resolveAllUses(bool ResolveUsers) { + if (UseMap.empty()) + return; + + if (!ResolveUsers) { + UseMap.clear(); + return; + } + + // Copy out uses since UseMap could get touched below. + typedef std::pair> UseTy; + SmallVector Uses(UseMap.begin(), UseMap.end()); + std::sort(Uses.begin(), Uses.end(), [](const UseTy &L, const UseTy &R) { + return L.second.second < R.second.second; + }); + UseMap.clear(); + for (const auto &Pair : Uses) { + auto Owner = Pair.second.first; + if (!Owner) + continue; + if (Owner.is()) + continue; + + // Resolve MDNodes that point at this. + auto *OwnerMD = dyn_cast(Owner.get()); + if (!OwnerMD) + continue; + if (OwnerMD->isResolved()) + continue; + OwnerMD->decrementUnresolvedOperandCount(); + } +} + +static Function *getLocalFunction(Value *V) { + assert(V && "Expected value"); + if (auto *A = dyn_cast(V)) + return A->getParent(); + if (BasicBlock *BB = cast(V)->getParent()) + return BB->getParent(); + return nullptr; +} + +ValueAsMetadata *ValueAsMetadata::get(Value *V) { + assert(V && "Unexpected null Value"); + + auto &Context = V->getContext(); + auto *&Entry = Context.pImpl->ValuesAsMetadata[V]; + if (!Entry) { + assert((isa(V) || isa(V) || isa(V)) && + "Expected constant or function-local value"); + assert(!V->NameAndIsUsedByMD.getInt() && + "Expected this to be the only metadata use"); + V->NameAndIsUsedByMD.setInt(true); + if (auto *C = dyn_cast(V)) + Entry = new ConstantAsMetadata(C); + else + Entry = new LocalAsMetadata(V); + } + + return Entry; +} + +ValueAsMetadata *ValueAsMetadata::getIfExists(Value *V) { + assert(V && "Unexpected null Value"); + return V->getContext().pImpl->ValuesAsMetadata.lookup(V); +} + +void ValueAsMetadata::handleDeletion(Value *V) { + assert(V && "Expected valid value"); + + auto &Store = V->getType()->getContext().pImpl->ValuesAsMetadata; + auto I = Store.find(V); + if (I == Store.end()) + return; + + // Remove old entry from the map. + ValueAsMetadata *MD = I->second; + assert(MD && "Expected valid metadata"); + assert(MD->getValue() == V && "Expected valid mapping"); + Store.erase(I); + + // Delete the metadata. + MD->replaceAllUsesWith(nullptr); + delete MD; +} + +void ValueAsMetadata::handleRAUW(Value *From, Value *To) { + assert(From && "Expected valid value"); + assert(To && "Expected valid value"); + assert(From != To && "Expected changed value"); + assert(From->getType() == To->getType() && "Unexpected type change"); + + LLVMContext &Context = From->getType()->getContext(); + auto &Store = Context.pImpl->ValuesAsMetadata; + auto I = Store.find(From); + if (I == Store.end()) { + assert(!From->NameAndIsUsedByMD.getInt() && + "Expected From not to be used by metadata"); + return; + } + + // Remove old entry from the map. + assert(From->NameAndIsUsedByMD.getInt() && + "Expected From to be used by metadata"); + From->NameAndIsUsedByMD.setInt(false); + ValueAsMetadata *MD = I->second; + assert(MD && "Expected valid metadata"); + assert(MD->getValue() == From && "Expected valid mapping"); + Store.erase(I); + + if (isa(MD)) { + if (auto *C = dyn_cast(To)) { + // Local became a constant. + MD->replaceAllUsesWith(ConstantAsMetadata::get(C)); + delete MD; + return; + } + if (getLocalFunction(From) && getLocalFunction(To) && + getLocalFunction(From) != getLocalFunction(To)) { + // Function changed. + MD->replaceAllUsesWith(nullptr); + delete MD; + return; + } + } else if (!isa(To)) { + // Changed to function-local value. + MD->replaceAllUsesWith(nullptr); + delete MD; + return; + } + + auto *&Entry = Store[To]; + if (Entry) { + // The target already exists. + MD->replaceAllUsesWith(Entry); + delete MD; + return; + } + + // Update MD in place (and update the map entry). + assert(!To->NameAndIsUsedByMD.getInt() && + "Expected this to be the only metadata use"); + To->NameAndIsUsedByMD.setInt(true); + MD->V = To; + Entry = MD; +} //===----------------------------------------------------------------------===// // MDString implementation. // -void MDString::anchor() { } - MDString *MDString::get(LLVMContext &Context, StringRef Str) { auto &Store = Context.pImpl->MDStringCache; auto I = Store.find(Str); @@ -44,7 +364,7 @@ MDString *MDString::get(LLVMContext &Context, StringRef Str) { return &I->second; auto *Entry = - StringMapEntry::Create(Str, Store.getAllocator(), Context); + StringMapEntry::Create(Str, Store.getAllocator(), MDString()); bool WasInserted = Store.insert(Entry); (void)WasInserted; assert(WasInserted && "Expected entry to be inserted"); @@ -58,341 +378,388 @@ StringRef MDString::getString() const { } //===----------------------------------------------------------------------===// -// MDNodeOperand implementation. +// MDNode implementation. // -// Use CallbackVH to hold MDNode operands. -namespace llvm { -class MDNodeOperand : public CallbackVH { - MDNode *getParent() { - MDNodeOperand *Cur = this; +void *MDNode::operator new(size_t Size, unsigned NumOps) { + void *Ptr = ::operator new(Size + NumOps * sizeof(MDOperand)); + MDOperand *O = static_cast(Ptr); + for (MDOperand *E = O + NumOps; O != E; ++O) + (void)new (O) MDOperand; + return O; +} + +void MDNode::operator delete(void *Mem) { + MDNode *N = static_cast(Mem); + MDOperand *O = static_cast(Mem); + for (MDOperand *E = O - N->NumOperands; O != E; --O) + (O - 1)->~MDOperand(); + ::operator delete(O); +} - while (Cur->getValPtrInt() != 1) - ++Cur; +MDNode::MDNode(LLVMContext &Context, unsigned ID, StorageType Storage, + ArrayRef Ops1, ArrayRef Ops2) + : Metadata(ID, Storage), NumOperands(Ops1.size() + Ops2.size()), + NumUnresolved(0), Context(Context) { + unsigned Op = 0; + for (Metadata *MD : Ops1) + setOperand(Op++, MD); + for (Metadata *MD : Ops2) + setOperand(Op++, MD); + + if (isDistinct()) + return; - assert(Cur->getValPtrInt() == 1 && - "Couldn't find the end of the operand list!"); - return reinterpret_cast(Cur + 1); - } + if (isUniqued()) + // Check whether any operands are unresolved, requiring re-uniquing. If + // not, don't support RAUW. + if (!countUnresolvedOperands()) + return; -public: - MDNodeOperand() {} - virtual ~MDNodeOperand(); + this->Context.makeReplaceable(make_unique(Context)); +} - void set(Value *V) { - unsigned IsLast = this->getValPtrInt(); - this->setValPtr(V); - this->setAsLastOperand(IsLast); +TempMDNode MDNode::clone() const { + switch (getMetadataID()) { + default: + llvm_unreachable("Invalid MDNode subclass"); +#define HANDLE_MDNODE_LEAF(CLASS) \ + case CLASS##Kind: \ + return cast(this)->cloneImpl(); +#include "llvm/IR/Metadata.def" } +} - /// \brief Accessor method to mark the operand as the first in the list. - void setAsLastOperand(unsigned I) { this->setValPtrInt(I); } +static bool isOperandUnresolved(Metadata *Op) { + if (auto *N = dyn_cast_or_null(Op)) + return !N->isResolved(); + return false; +} - void deleted() override; - void allUsesReplacedWith(Value *NV) override; -}; -} // end namespace llvm. +unsigned MDNode::countUnresolvedOperands() { + assert(NumUnresolved == 0 && "Expected unresolved ops to be uncounted"); + NumUnresolved = std::count_if(op_begin(), op_end(), isOperandUnresolved); + return NumUnresolved; +} -// Provide out-of-line definition to prevent weak vtable. -MDNodeOperand::~MDNodeOperand() {} +void MDNode::makeUniqued() { + assert(isTemporary() && "Expected this to be temporary"); + assert(!isResolved() && "Expected this to be unresolved"); -void MDNodeOperand::deleted() { - getParent()->replaceOperand(this, nullptr); -} + // Enable uniquing callbacks. + for (auto &Op : mutable_operands()) + Op.reset(Op.get(), this); + + // Make this 'uniqued'. + Storage = Uniqued; + if (!countUnresolvedOperands()) + resolve(); -void MDNodeOperand::allUsesReplacedWith(Value *NV) { - getParent()->replaceOperand(this, NV); + assert(isUniqued() && "Expected this to be uniqued"); } -//===----------------------------------------------------------------------===// -// MDNode implementation. -// +void MDNode::makeDistinct() { + assert(isTemporary() && "Expected this to be temporary"); + assert(!isResolved() && "Expected this to be unresolved"); + + // Pretend to be uniqued, resolve the node, and then store in distinct table. + Storage = Uniqued; + resolve(); + storeDistinctInContext(); -/// \brief Get the MDNodeOperand's coallocated on the end of the MDNode. -static MDNodeOperand *getOperandPtr(MDNode *N, unsigned Op) { - // Use <= instead of < to permit a one-past-the-end address. - assert(Op <= N->getNumOperands() && "Invalid operand number"); - return reinterpret_cast(N) - N->getNumOperands() + Op; + assert(isDistinct() && "Expected this to be distinct"); + assert(isResolved() && "Expected this to be resolved"); } -void MDNode::replaceOperandWith(unsigned i, Value *Val) { - MDNodeOperand *Op = getOperandPtr(this, i); - replaceOperand(Op, Val); +void MDNode::resolve() { + assert(isUniqued() && "Expected this to be uniqued"); + assert(!isResolved() && "Expected this to be unresolved"); + + // Move the map, so that this immediately looks resolved. + auto Uses = Context.takeReplaceableUses(); + NumUnresolved = 0; + assert(isResolved() && "Expected this to be resolved"); + + // Drop RAUW support. + Uses->resolveAllUses(); } -void *MDNode::operator new(size_t Size, unsigned NumOps) { - void *Ptr = ::operator new(Size + NumOps * sizeof(MDNodeOperand)); - MDNodeOperand *Op = static_cast(Ptr); - if (NumOps) { - MDNodeOperand *Last = Op + NumOps; - for (; Op != Last; ++Op) - new (Op) MDNodeOperand(); - (Op - 1)->setAsLastOperand(1); - } - return Op; +void MDNode::resolveAfterOperandChange(Metadata *Old, Metadata *New) { + assert(NumUnresolved != 0 && "Expected unresolved operands"); + + // Check if an operand was resolved. + if (!isOperandUnresolved(Old)) { + if (isOperandUnresolved(New)) + // An operand was un-resolved! + ++NumUnresolved; + } else if (!isOperandUnresolved(New)) + decrementUnresolvedOperandCount(); } -void MDNode::operator delete(void *Mem) { - MDNode *N = static_cast(Mem); - MDNodeOperand *Op = static_cast(Mem); - for (unsigned I = 0, E = N->NumOperands; I != E; ++I) - (--Op)->~MDNodeOperand(); - ::operator delete(Op); +void MDNode::decrementUnresolvedOperandCount() { + if (!--NumUnresolved) + // Last unresolved operand has just been resolved. + resolve(); } -MDNode::MDNode(LLVMContext &C, unsigned ID, ArrayRef Vals, - bool isFunctionLocal) - : Metadata(C, ID) { - NumOperands = Vals.size(); +void MDNode::resolveCycles() { + if (isResolved()) + return; - if (isFunctionLocal) - setValueSubclassData(getSubclassDataFromValue() | FunctionLocalBit); + // Resolve this node immediately. + resolve(); - // Initialize the operand list. - unsigned i = 0; - for (MDNodeOperand *Op = getOperandPtr(this, 0), *E = Op + NumOperands; - Op != E; ++Op, ++i) - Op->set(Vals[i]); -} + // Resolve all operands. + for (const auto &Op : operands()) { + auto *N = dyn_cast_or_null(Op); + if (!N) + continue; -GenericMDNode::~GenericMDNode() { - LLVMContextImpl *pImpl = getType()->getContext().pImpl; - if (isNotUniqued()) { - pImpl->NonUniquedMDNodes.erase(this); - } else { - pImpl->MDNodeSet.erase(this); + assert(!N->isTemporary() && + "Expected all forward declarations to be resolved"); + if (!N->isResolved()) + N->resolveCycles(); } } -void GenericMDNode::dropAllReferences() { - for (MDNodeOperand *Op = getOperandPtr(this, 0), *E = Op + NumOperands; - Op != E; ++Op) - Op->set(nullptr); +static bool hasSelfReference(MDNode *N) { + for (Metadata *MD : N->operands()) + if (MD == N) + return true; + return false; +} + +MDNode *MDNode::replaceWithPermanentImpl() { + if (hasSelfReference(this)) + return replaceWithDistinctImpl(); + return replaceWithUniquedImpl(); } -static const Function *getFunctionForValue(Value *V) { - if (!V) return nullptr; - if (Instruction *I = dyn_cast(V)) { - BasicBlock *BB = I->getParent(); - return BB ? BB->getParent() : nullptr; +MDNode *MDNode::replaceWithUniquedImpl() { + // Try to uniquify in place. + MDNode *UniquedNode = uniquify(); + + if (UniquedNode == this) { + makeUniqued(); + return this; } - if (Argument *A = dyn_cast(V)) - return A->getParent(); - if (BasicBlock *BB = dyn_cast(V)) - return BB->getParent(); - if (MDNode *MD = dyn_cast(V)) - return MD->getFunction(); - return nullptr; + + // Collision, so RAUW instead. + replaceAllUsesWith(UniquedNode); + deleteAsSubclass(); + return UniquedNode; } -#ifndef NDEBUG -static const Function *assertLocalFunction(const MDNode *N) { - if (!N->isFunctionLocal()) return nullptr; +MDNode *MDNode::replaceWithDistinctImpl() { + makeDistinct(); + return this; +} - // FIXME: This does not handle cyclic function local metadata. - const Function *F = nullptr, *NewF = nullptr; - for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { - if (Value *V = N->getOperand(i)) { - if (MDNode *MD = dyn_cast(V)) - NewF = assertLocalFunction(MD); - else - NewF = getFunctionForValue(V); - } - if (!F) - F = NewF; - else - assert((NewF == nullptr || F == NewF) && - "inconsistent function-local metadata"); - } - return F; -} -#endif - -// getFunction - If this metadata is function-local and recursively has a -// function-local operand, return the first such operand's parent function. -// Otherwise, return null. getFunction() should not be used for performance- -// critical code because it recursively visits all the MDNode's operands. -const Function *MDNode::getFunction() const { -#ifndef NDEBUG - return assertLocalFunction(this); -#else - if (!isFunctionLocal()) return nullptr; - for (unsigned i = 0, e = getNumOperands(); i != e; ++i) - if (const Function *F = getFunctionForValue(getOperand(i))) - return F; - return nullptr; -#endif +void MDTuple::recalculateHash() { + setHash(MDTupleInfo::KeyTy::calculateHash(this)); } -/// \brief Check if the Value would require a function-local MDNode. -static bool isFunctionLocalValue(Value *V) { - return isa(V) || isa(V) || isa(V) || - (isa(V) && cast(V)->isFunctionLocal()); +void MDNode::dropAllReferences() { + for (unsigned I = 0, E = NumOperands; I != E; ++I) + setOperand(I, nullptr); + if (!isResolved()) { + Context.getReplaceableUses()->resolveAllUses(/* ResolveUsers */ false); + (void)Context.takeReplaceableUses(); + } } -MDNode *MDNode::getMDNode(LLVMContext &Context, ArrayRef Vals, - FunctionLocalness FL, bool Insert) { - auto &Store = Context.pImpl->MDNodeSet; +void MDNode::handleChangedOperand(void *Ref, Metadata *New) { + unsigned Op = static_cast(Ref) - op_begin(); + assert(Op < getNumOperands() && "Expected valid operand"); - GenericMDNodeInfo::KeyTy Key(Vals); - auto I = Store.find_as(Key); - if (I != Store.end()) - return *I; - if (!Insert) - return nullptr; + if (!isUniqued()) { + // This node is not uniqued. Just set the operand and be done with it. + setOperand(Op, New); + return; + } - bool isFunctionLocal = false; - switch (FL) { - case FL_Unknown: - for (Value *V : Vals) { - if (!V) continue; - if (isFunctionLocalValue(V)) { - isFunctionLocal = true; - break; - } - } - break; - case FL_No: - isFunctionLocal = false; - break; - case FL_Yes: - isFunctionLocal = true; + // This node is uniqued. + eraseFromStore(); + + Metadata *Old = getOperand(Op); + setOperand(Op, New); + + // Drop uniquing for self-reference cycles. + if (New == this) { + if (!isResolved()) + resolve(); + storeDistinctInContext(); + return; + } + + // Re-unique the node. + auto *Uniqued = uniquify(); + if (Uniqued == this) { + if (!isResolved()) + resolveAfterOperandChange(Old, New); + return; + } + + // Collision. + if (!isResolved()) { + // Still unresolved, so RAUW. + // + // First, clear out all operands to prevent any recursion (similar to + // dropAllReferences(), but we still need the use-list). + for (unsigned O = 0, E = getNumOperands(); O != E; ++O) + setOperand(O, nullptr); + Context.getReplaceableUses()->replaceAllUsesWith(Uniqued); + deleteAsSubclass(); + return; + } + + // Store in non-uniqued form if RAUW isn't possible. + storeDistinctInContext(); +} + +void MDNode::deleteAsSubclass() { + switch (getMetadataID()) { + default: + llvm_unreachable("Invalid subclass of MDNode"); +#define HANDLE_MDNODE_LEAF(CLASS) \ + case CLASS##Kind: \ + delete cast(this); \ break; +#include "llvm/IR/Metadata.def" } +} - // Coallocate space for the node and Operands together, then placement new. - GenericMDNode *N = - new (Vals.size()) GenericMDNode(Context, Vals, isFunctionLocal); +template +static T *uniquifyImpl(T *N, DenseSet &Store) { + if (T *U = getUniqued(Store, N)) + return U; - N->Hash = Key.Hash; Store.insert(N); return N; } -MDNode *MDNode::get(LLVMContext &Context, ArrayRef Vals) { - return getMDNode(Context, Vals, FL_Unknown); -} +template struct MDNode::HasCachedHash { + typedef char Yes[1]; + typedef char No[2]; + template struct SFINAE {}; -MDNode *MDNode::getWhenValsUnresolved(LLVMContext &Context, - ArrayRef Vals, - bool isFunctionLocal) { - return getMDNode(Context, Vals, isFunctionLocal ? FL_Yes : FL_No); -} + template + static Yes &check(SFINAE *); + template static No &check(...); -MDNode *MDNode::getIfExists(LLVMContext &Context, ArrayRef Vals) { - return getMDNode(Context, Vals, FL_Unknown, false); -} + static const bool value = sizeof(check(nullptr)) == sizeof(Yes); +}; -MDNode *MDNode::getTemporary(LLVMContext &Context, ArrayRef Vals) { - MDNode *N = new (Vals.size()) MDNodeFwdDecl(Context, Vals, FL_No); - N->setValueSubclassData(N->getSubclassDataFromValue() | NotUniquedBit); - LeakDetector::addGarbageObject(N); - return N; +MDNode *MDNode::uniquify() { + assert(!hasSelfReference(this) && "Cannot uniquify a self-referencing node"); + + // Try to insert into uniquing store. + switch (getMetadataID()) { + default: + llvm_unreachable("Invalid subclass of MDNode"); +#define HANDLE_MDNODE_LEAF(CLASS) \ + case CLASS##Kind: { \ + CLASS *SubclassThis = cast(this); \ + std::integral_constant::value> \ + ShouldRecalculateHash; \ + dispatchRecalculateHash(SubclassThis, ShouldRecalculateHash); \ + return uniquifyImpl(SubclassThis, getContext().pImpl->CLASS##s); \ + } +#include "llvm/IR/Metadata.def" + } } -void MDNode::deleteTemporary(MDNode *N) { - assert(N->use_empty() && "Temporary MDNode has uses!"); - assert(isa(N) && "Expected forward declaration"); - assert((N->getSubclassDataFromValue() & NotUniquedBit) && - "Temporary MDNode does not have NotUniquedBit set!"); - LeakDetector::removeGarbageObject(N); - delete cast(N); -} - -/// \brief Return specified operand. -Value *MDNode::getOperand(unsigned i) const { - assert(i < getNumOperands() && "Invalid operand number"); - return *getOperandPtr(const_cast(this), i); -} - -void MDNode::setIsNotUniqued() { - setValueSubclassData(getSubclassDataFromValue() | NotUniquedBit); - LLVMContextImpl *pImpl = getType()->getContext().pImpl; - auto *G = cast(this); - G->Hash = 0; - pImpl->NonUniquedMDNodes.insert(G); -} - -// Replace value from this node's operand list. -void MDNode::replaceOperand(MDNodeOperand *Op, Value *To) { - Value *From = *Op; - - // If is possible that someone did GV->RAUW(inst), replacing a global variable - // with an instruction or some other function-local object. If this is a - // non-function-local MDNode, it can't point to a function-local object. - // Handle this case by implicitly dropping the MDNode reference to null. - // Likewise if the MDNode is function-local but for a different function. - if (To && isFunctionLocalValue(To)) { - if (!isFunctionLocal()) - To = nullptr; - else { - const Function *F = getFunction(); - const Function *FV = getFunctionForValue(To); - // Metadata can be function-local without having an associated function. - // So only consider functions to have changed if non-null. - if (F && FV && F != FV) - To = nullptr; - } +void MDNode::eraseFromStore() { + switch (getMetadataID()) { + default: + llvm_unreachable("Invalid subclass of MDNode"); +#define HANDLE_MDNODE_LEAF(CLASS) \ + case CLASS##Kind: \ + getContext().pImpl->CLASS##s.erase(cast(this)); \ + break; +#include "llvm/IR/Metadata.def" } - - if (From == To) - return; +} - // If this node is already not being uniqued (because one of the operands - // already went to null), then there is nothing else to do here. - if (isNotUniqued()) { - Op->set(To); - return; +MDTuple *MDTuple::getImpl(LLVMContext &Context, ArrayRef MDs, + StorageType Storage, bool ShouldCreate) { + unsigned Hash = 0; + if (Storage == Uniqued) { + MDTupleInfo::KeyTy Key(MDs); + if (auto *N = getUniqued(Context.pImpl->MDTuples, Key)) + return N; + if (!ShouldCreate) + return nullptr; + Hash = Key.getHash(); + } else { + assert(ShouldCreate && "Expected non-uniqued nodes to always be created"); } - auto &Store = getContext().pImpl->MDNodeSet; - auto *N = cast(this); + return storeImpl(new (MDs.size()) MDTuple(Context, Storage, Hash, MDs), + Storage, Context.pImpl->MDTuples); +} - // Remove "this" from the context map. - Store.erase(N); +void MDNode::deleteTemporary(MDNode *N) { + assert(N->isTemporary() && "Expected temporary node"); + N->replaceAllUsesWith(nullptr); + N->deleteAsSubclass(); +} - // Update the operand. - Op->set(To); +void MDNode::storeDistinctInContext() { + assert(isResolved() && "Expected resolved nodes"); + Storage = Distinct; + + // Reset the hash. + switch (getMetadataID()) { + default: + llvm_unreachable("Invalid subclass of MDNode"); +#define HANDLE_MDNODE_LEAF(CLASS) \ + case CLASS##Kind: { \ + std::integral_constant::value> ShouldResetHash; \ + dispatchResetHash(cast(this), ShouldResetHash); \ + break; \ + } +#include "llvm/IR/Metadata.def" + } + + getContext().pImpl->DistinctMDNodes.insert(this); +} - // If we are dropping an argument to null, we choose to not unique the MDNode - // anymore. This commonly occurs during destruction, and uniquing these - // brings little reuse. Also, this means we don't need to include - // isFunctionLocal bits in the hash for MDNodes. - if (!To) { - setIsNotUniqued(); +void MDNode::replaceOperandWith(unsigned I, Metadata *New) { + if (getOperand(I) == New) return; - } - // Now that the node is out of the table, get ready to reinsert it. First, - // check to see if another node with the same operands already exists in the - // set. If so, then this node is redundant. - SmallVector Vals; - GenericMDNodeInfo::KeyTy Key(N, Vals); - auto I = Store.find_as(Key); - if (I != Store.end()) { - N->replaceAllUsesWith(*I); - delete N; + if (!isUniqued()) { + setOperand(I, New); return; } - N->Hash = Key.Hash; - Store.insert(N); + handleChangedOperand(mutable_begin() + I, New); +} - // If this MDValue was previously function-local but no longer is, clear - // its function-local flag. - if (isFunctionLocal() && !isFunctionLocalValue(To)) { - bool isStillFunctionLocal = false; - for (unsigned i = 0, e = getNumOperands(); i != e; ++i) { - Value *V = getOperand(i); - if (!V) continue; - if (isFunctionLocalValue(V)) { - isStillFunctionLocal = true; - break; +void MDNode::setOperand(unsigned I, Metadata *New) { + assert(I < NumOperands); + mutable_begin()[I].reset(New, isUniqued() ? this : nullptr); +} + +/// \brief Get a node, or a self-reference that looks like it. +/// +/// Special handling for finding self-references, for use by \a +/// MDNode::concatenate() and \a MDNode::intersect() to maintain behaviour from +/// when self-referencing nodes were still uniqued. If the first operand has +/// the same operands as \c Ops, return the first operand instead. +static MDNode *getOrSelfReference(LLVMContext &Context, + ArrayRef Ops) { + if (!Ops.empty()) + if (MDNode *N = dyn_cast_or_null(Ops[0])) + if (N->getNumOperands() == Ops.size() && N == N->getOperand(0)) { + for (unsigned I = 1, E = Ops.size(); I != E; ++I) + if (Ops[I] != N->getOperand(I)) + return MDNode::get(Context, Ops); + return N; } - } - if (!isStillFunctionLocal) - setValueSubclassData(getSubclassDataFromValue() & ~FunctionLocalBit); - } + + return MDNode::get(Context, Ops); } MDNode *MDNode::concatenate(MDNode *A, MDNode *B) { @@ -401,41 +768,50 @@ MDNode *MDNode::concatenate(MDNode *A, MDNode *B) { if (!B) return A; - SmallVector Vals(A->getNumOperands() + - B->getNumOperands()); - - unsigned j = 0; - for (unsigned i = 0, ie = A->getNumOperands(); i != ie; ++i) - Vals[j++] = A->getOperand(i); - for (unsigned i = 0, ie = B->getNumOperands(); i != ie; ++i) - Vals[j++] = B->getOperand(i); + SmallVector MDs; + MDs.reserve(A->getNumOperands() + B->getNumOperands()); + MDs.append(A->op_begin(), A->op_end()); + MDs.append(B->op_begin(), B->op_end()); - return MDNode::get(A->getContext(), Vals); + // FIXME: This preserves long-standing behaviour, but is it really the right + // behaviour? Or was that an unintended side-effect of node uniquing? + return getOrSelfReference(A->getContext(), MDs); } MDNode *MDNode::intersect(MDNode *A, MDNode *B) { if (!A || !B) return nullptr; - SmallVector Vals; - for (unsigned i = 0, ie = A->getNumOperands(); i != ie; ++i) { - Value *V = A->getOperand(i); - for (unsigned j = 0, je = B->getNumOperands(); j != je; ++j) - if (V == B->getOperand(j)) { - Vals.push_back(V); - break; - } - } + SmallVector MDs; + for (Metadata *MD : A->operands()) + if (std::find(B->op_begin(), B->op_end(), MD) != B->op_end()) + MDs.push_back(MD); + + // FIXME: This preserves long-standing behaviour, but is it really the right + // behaviour? Or was that an unintended side-effect of node uniquing? + return getOrSelfReference(A->getContext(), MDs); +} + +MDNode *MDNode::getMostGenericAliasScope(MDNode *A, MDNode *B) { + if (!A || !B) + return nullptr; - return MDNode::get(A->getContext(), Vals); + SmallVector MDs(B->op_begin(), B->op_end()); + for (Metadata *MD : A->operands()) + if (std::find(B->op_begin(), B->op_end(), MD) == B->op_end()) + MDs.push_back(MD); + + // FIXME: This preserves long-standing behaviour, but is it really the right + // behaviour? Or was that an unintended side-effect of node uniquing? + return getOrSelfReference(A->getContext(), MDs); } MDNode *MDNode::getMostGenericFPMath(MDNode *A, MDNode *B) { if (!A || !B) return nullptr; - APFloat AVal = cast(A->getOperand(0))->getValueAPF(); - APFloat BVal = cast(B->getOperand(0))->getValueAPF(); + APFloat AVal = mdconst::extract(A->getOperand(0))->getValueAPF(); + APFloat BVal = mdconst::extract(B->getOperand(0))->getValueAPF(); if (AVal.compare(BVal) == APFloat::cmpLessThan) return A; return B; @@ -449,25 +825,27 @@ static bool canBeMerged(const ConstantRange &A, const ConstantRange &B) { return !A.intersectWith(B).isEmptySet() || isContiguous(A, B); } -static bool tryMergeRange(SmallVectorImpl &EndPoints, ConstantInt *Low, - ConstantInt *High) { +static bool tryMergeRange(SmallVectorImpl &EndPoints, + ConstantInt *Low, ConstantInt *High) { ConstantRange NewRange(Low->getValue(), High->getValue()); unsigned Size = EndPoints.size(); - APInt LB = cast(EndPoints[Size - 2])->getValue(); - APInt LE = cast(EndPoints[Size - 1])->getValue(); + APInt LB = EndPoints[Size - 2]->getValue(); + APInt LE = EndPoints[Size - 1]->getValue(); ConstantRange LastRange(LB, LE); if (canBeMerged(NewRange, LastRange)) { ConstantRange Union = LastRange.unionWith(NewRange); Type *Ty = High->getType(); - EndPoints[Size - 2] = ConstantInt::get(Ty, Union.getLower()); - EndPoints[Size - 1] = ConstantInt::get(Ty, Union.getUpper()); + EndPoints[Size - 2] = + cast(ConstantInt::get(Ty, Union.getLower())); + EndPoints[Size - 1] = + cast(ConstantInt::get(Ty, Union.getUpper())); return true; } return false; } -static void addRange(SmallVectorImpl &EndPoints, ConstantInt *Low, - ConstantInt *High) { +static void addRange(SmallVectorImpl &EndPoints, + ConstantInt *Low, ConstantInt *High) { if (!EndPoints.empty()) if (tryMergeRange(EndPoints, Low, High)) return; @@ -489,31 +867,33 @@ MDNode *MDNode::getMostGenericRange(MDNode *A, MDNode *B) { // First, walk both lists in older of the lower boundary of each interval. // At each step, try to merge the new interval to the last one we adedd. - SmallVector EndPoints; + SmallVector EndPoints; int AI = 0; int BI = 0; int AN = A->getNumOperands() / 2; int BN = B->getNumOperands() / 2; while (AI < AN && BI < BN) { - ConstantInt *ALow = cast(A->getOperand(2 * AI)); - ConstantInt *BLow = cast(B->getOperand(2 * BI)); + ConstantInt *ALow = mdconst::extract(A->getOperand(2 * AI)); + ConstantInt *BLow = mdconst::extract(B->getOperand(2 * BI)); if (ALow->getValue().slt(BLow->getValue())) { - addRange(EndPoints, ALow, cast(A->getOperand(2 * AI + 1))); + addRange(EndPoints, ALow, + mdconst::extract(A->getOperand(2 * AI + 1))); ++AI; } else { - addRange(EndPoints, BLow, cast(B->getOperand(2 * BI + 1))); + addRange(EndPoints, BLow, + mdconst::extract(B->getOperand(2 * BI + 1))); ++BI; } } while (AI < AN) { - addRange(EndPoints, cast(A->getOperand(2 * AI)), - cast(A->getOperand(2 * AI + 1))); + addRange(EndPoints, mdconst::extract(A->getOperand(2 * AI)), + mdconst::extract(A->getOperand(2 * AI + 1))); ++AI; } while (BI < BN) { - addRange(EndPoints, cast(B->getOperand(2 * BI)), - cast(B->getOperand(2 * BI + 1))); + addRange(EndPoints, mdconst::extract(B->getOperand(2 * BI)), + mdconst::extract(B->getOperand(2 * BI + 1))); ++BI; } @@ -521,8 +901,8 @@ MDNode *MDNode::getMostGenericRange(MDNode *A, MDNode *B) { // the last and first ones. unsigned Size = EndPoints.size(); if (Size > 4) { - ConstantInt *FB = cast(EndPoints[0]); - ConstantInt *FE = cast(EndPoints[1]); + ConstantInt *FB = EndPoints[0]; + ConstantInt *FE = EndPoints[1]; if (tryMergeRange(EndPoints, FB, FE)) { for (unsigned i = 0; i < Size - 2; ++i) { EndPoints[i] = EndPoints[i + 2]; @@ -534,26 +914,29 @@ MDNode *MDNode::getMostGenericRange(MDNode *A, MDNode *B) { // If in the end we have a single range, it is possible that it is now the // full range. Just drop the metadata in that case. if (EndPoints.size() == 2) { - ConstantRange Range(cast(EndPoints[0])->getValue(), - cast(EndPoints[1])->getValue()); + ConstantRange Range(EndPoints[0]->getValue(), EndPoints[1]->getValue()); if (Range.isFullSet()) return nullptr; } - return MDNode::get(A->getContext(), EndPoints); + SmallVector MDs; + MDs.reserve(EndPoints.size()); + for (auto *I : EndPoints) + MDs.push_back(ConstantAsMetadata::get(I)); + return MDNode::get(A->getContext(), MDs); } //===----------------------------------------------------------------------===// // NamedMDNode implementation. // -static SmallVector, 4> &getNMDOps(void *Operands) { - return *(SmallVector, 4> *)Operands; +static SmallVector &getNMDOps(void *Operands) { + return *(SmallVector *)Operands; } NamedMDNode::NamedMDNode(const Twine &N) : Name(N.str()), Parent(nullptr), - Operands(new SmallVector, 4>()) {} + Operands(new SmallVector()) {} NamedMDNode::~NamedMDNode() { dropAllReferences(); @@ -566,13 +949,15 @@ unsigned NamedMDNode::getNumOperands() const { MDNode *NamedMDNode::getOperand(unsigned i) const { assert(i < getNumOperands() && "Invalid Operand number!"); - return &*getNMDOps(Operands)[i]; + auto *N = getNMDOps(Operands)[i].get(); + return cast_or_null(N); } -void NamedMDNode::addOperand(MDNode *M) { - assert(!M->isFunctionLocal() && - "NamedMDNode operands must not be function-local!"); - getNMDOps(Operands).push_back(TrackingVH(M)); +void NamedMDNode::addOperand(MDNode *M) { getNMDOps(Operands).emplace_back(M); } + +void NamedMDNode::setOperand(unsigned I, MDNode *New) { + assert(I < getNumOperands() && "Invalid operand number"); + getNMDOps(Operands)[I].reset(New); } void NamedMDNode::eraseFromParent() { @@ -612,35 +997,26 @@ void Instruction::dropUnknownMetadata(ArrayRef KnownIDs) { if (!hasMetadataHashEntry()) return; // Nothing to remove! - DenseMap &MetadataStore = - getContext().pImpl->MetadataStore; + auto &InstructionMetadata = getContext().pImpl->InstructionMetadata; if (KnownSet.empty()) { // Just drop our entry at the store. - MetadataStore.erase(this); + InstructionMetadata.erase(this); setHasMetadataHashEntry(false); return; } - LLVMContextImpl::MDMapTy &Info = MetadataStore[this]; - unsigned I; - unsigned E; - // Walk the array and drop any metadata we don't know. - for (I = 0, E = Info.size(); I != E;) { - if (KnownSet.count(Info[I].first)) { - ++I; - continue; - } + auto &Info = InstructionMetadata[this]; + Info.erase(std::remove_if( + Info.begin(), Info.end(), + [&KnownSet](const std::pair &I) { + return !KnownSet.count(I.first); + }), + Info.end()); - Info[I] = Info.back(); - Info.pop_back(); - --E; - } - assert(E == Info.size()); - - if (E == 0) { + if (Info.empty()) { // Drop our entry at the store. - MetadataStore.erase(this); + InstructionMetadata.erase(this); setHasMetadataHashEntry(false); } } @@ -654,13 +1030,13 @@ void Instruction::setMetadata(unsigned KindID, MDNode *Node) { // Handle 'dbg' as a special case since it is not stored in the hash table. if (KindID == LLVMContext::MD_dbg) { - DbgLoc = DebugLoc::getFromDILocation(Node); + DbgLoc = DebugLoc(Node); return; } // Handle the case when we're adding/updating metadata on an instruction. if (Node) { - LLVMContextImpl::MDMapTy &Info = getContext().pImpl->MetadataStore[this]; + auto &Info = getContext().pImpl->InstructionMetadata[this]; assert(!Info.empty() == hasMetadataHashEntry() && "HasMetadata bit is wonked"); if (Info.empty()) { @@ -669,27 +1045,28 @@ void Instruction::setMetadata(unsigned KindID, MDNode *Node) { // Handle replacement of an existing value. for (auto &P : Info) if (P.first == KindID) { - P.second = Node; + P.second.reset(Node); return; } } // No replacement, just add it to the list. - Info.push_back(std::make_pair(KindID, Node)); + Info.emplace_back(std::piecewise_construct, std::make_tuple(KindID), + std::make_tuple(Node)); return; } // Otherwise, we're removing metadata from an instruction. assert((hasMetadataHashEntry() == - (getContext().pImpl->MetadataStore.count(this) > 0)) && + (getContext().pImpl->InstructionMetadata.count(this) > 0)) && "HasMetadata bit out of date!"); if (!hasMetadataHashEntry()) return; // Nothing to remove! - LLVMContextImpl::MDMapTy &Info = getContext().pImpl->MetadataStore[this]; + auto &Info = getContext().pImpl->InstructionMetadata[this]; // Common case is removing the only entry. if (Info.size() == 1 && Info[0].first == KindID) { - getContext().pImpl->MetadataStore.erase(this); + getContext().pImpl->InstructionMetadata.erase(this); setHasMetadataHashEntry(false); return; } @@ -697,7 +1074,7 @@ void Instruction::setMetadata(unsigned KindID, MDNode *Node) { // Handle removal of an existing value. for (unsigned i = 0, e = Info.size(); i != e; ++i) if (Info[i].first == KindID) { - Info[i] = Info.back(); + Info[i] = std::move(Info.back()); Info.pop_back(); assert(!Info.empty() && "Removing last entry should be handled above"); return; @@ -714,11 +1091,11 @@ void Instruction::setAAMetadata(const AAMDNodes &N) { MDNode *Instruction::getMetadataImpl(unsigned KindID) const { // Handle 'dbg' as a special case since it is not stored in the hash table. if (KindID == LLVMContext::MD_dbg) - return DbgLoc.getAsMDNode(getContext()); - + return DbgLoc.getAsMDNode(); + if (!hasMetadataHashEntry()) return nullptr; - - LLVMContextImpl::MDMapTy &Info = getContext().pImpl->MetadataStore[this]; + + auto &Info = getContext().pImpl->InstructionMetadata[this]; assert(!Info.empty() && "bit out of sync with hash table"); for (const auto &I : Info) @@ -732,20 +1109,21 @@ void Instruction::getAllMetadataImpl( Result.clear(); // Handle 'dbg' as a special case since it is not stored in the hash table. - if (!DbgLoc.isUnknown()) { - Result.push_back(std::make_pair((unsigned)LLVMContext::MD_dbg, - DbgLoc.getAsMDNode(getContext()))); + if (DbgLoc) { + Result.push_back( + std::make_pair((unsigned)LLVMContext::MD_dbg, DbgLoc.getAsMDNode())); if (!hasMetadataHashEntry()) return; } - + assert(hasMetadataHashEntry() && - getContext().pImpl->MetadataStore.count(this) && + getContext().pImpl->InstructionMetadata.count(this) && "Shouldn't have called this"); - const LLVMContextImpl::MDMapTy &Info = - getContext().pImpl->MetadataStore.find(this)->second; + const auto &Info = getContext().pImpl->InstructionMetadata.find(this)->second; assert(!Info.empty() && "Shouldn't have called this"); - Result.append(Info.begin(), Info.end()); + Result.reserve(Result.size() + Info.size()); + for (auto &I : Info) + Result.push_back(std::make_pair(I.first, cast(I.second.get()))); // Sort the resulting array so it is stable. if (Result.size() > 1) @@ -756,12 +1134,13 @@ void Instruction::getAllMetadataOtherThanDebugLocImpl( SmallVectorImpl> &Result) const { Result.clear(); assert(hasMetadataHashEntry() && - getContext().pImpl->MetadataStore.count(this) && + getContext().pImpl->InstructionMetadata.count(this) && "Shouldn't have called this"); - const LLVMContextImpl::MDMapTy &Info = - getContext().pImpl->MetadataStore.find(this)->second; + const auto &Info = getContext().pImpl->InstructionMetadata.find(this)->second; assert(!Info.empty() && "Shouldn't have called this"); - Result.append(Info.begin(), Info.end()); + Result.reserve(Result.size() + Info.size()); + for (auto &I : Info) + Result.push_back(std::make_pair(I.first, cast(I.second.get()))); // Sort the resulting array so it is stable. if (Result.size() > 1) @@ -772,7 +1151,6 @@ void Instruction::getAllMetadataOtherThanDebugLocImpl( /// this instruction. void Instruction::clearMetadataHashEntries() { assert(hasMetadataHashEntry() && "Caller should check"); - getContext().pImpl->MetadataStore.erase(this); + getContext().pImpl->InstructionMetadata.erase(this); setHasMetadataHashEntry(false); } -