X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FIR%2FMetadata.cpp;h=936c129662dbeafddc50ddafb9d789d3b08275f1;hb=7ecec5b0d4c1ef145b2382f9504bab3c6b6907eb;hp=d7d64641bdb2f2daf86dbec1d496426b3c30e0c4;hpb=2c7c54c86c0619a0d3b9e22a6990b075fd174529;p=oota-llvm.git diff --git a/lib/IR/Metadata.cpp b/lib/IR/Metadata.cpp index d7d64641bdb..936c129662d 100644 --- a/lib/IR/Metadata.cpp +++ b/lib/IR/Metadata.cpp @@ -25,393 +25,682 @@ #include "llvm/IR/LeakDetector.h" #include "llvm/IR/Module.h" #include "llvm/IR/ValueHandle.h" -using namespace llvm; - -//===----------------------------------------------------------------------===// -// MDString implementation. -// -void MDString::anchor() { } +using namespace llvm; -MDString::MDString(LLVMContext &C) - : Value(Type::getMetadataTy(C), Value::MDStringVal) {} +MetadataAsValue::MetadataAsValue(Type *Ty, Metadata *MD) + : Value(Ty, MetadataAsValueVal), MD(MD) { + track(); +} -MDString *MDString::get(LLVMContext &Context, StringRef Str) { - LLVMContextImpl *pImpl = Context.pImpl; - StringMapEntry &Entry = - pImpl->MDStringCache.GetOrCreateValue(Str); - Value *&S = Entry.getValue(); - if (!S) S = new MDString(Context); - S->setValueName(&Entry); - return cast(S); +MetadataAsValue::~MetadataAsValue() { + getType()->getContext().pImpl->MetadataAsValues.erase(MD); + untrack(); } -//===----------------------------------------------------------------------===// -// MDNodeOperand implementation. -// +/// \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; +} -// Use CallbackVH to hold MDNode operands. -namespace llvm { -class MDNodeOperand : public CallbackVH { - MDNode *getParent() { - MDNodeOperand *Cur = this; +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; +} - while (Cur->getValPtrInt() != 1) - --Cur; +MetadataAsValue *MetadataAsValue::getIfExists(LLVMContext &Context, + Metadata *MD) { + MD = canonicalizeMetadataForValue(Context, MD); + auto &Store = Context.pImpl->MetadataAsValues; + auto I = Store.find(MD); + return I == Store.end() ? nullptr : I->second; +} - assert(Cur->getValPtrInt() == 1 && - "Couldn't find the beginning of the operand list!"); - return reinterpret_cast(Cur) - 1; +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; } -public: - MDNodeOperand(Value *V) : CallbackVH(V) {} - virtual ~MDNodeOperand(); - - void set(Value *V) { - unsigned IsFirst = this->getValPtrInt(); - this->setValPtr(V); - this->setAsFirstOperand(IsFirst); - } + this->MD = MD; + track(); + Entry = this; +} - /// setAsFirstOperand - Accessor method to mark the operand as the first in - /// the list. - void setAsFirstOperand(unsigned V) { this->setValPtrInt(V); } +void MetadataAsValue::track() { + if (MD) + MetadataTracking::track(&MD, *MD, *this); +} - void deleted() override; - void allUsesReplacedWith(Value *NV) override; -}; -} // end namespace llvm. +void MetadataAsValue::untrack() { + if (MD) + MetadataTracking::untrack(MD); +} -// Provide out-of-line definition to prevent weak vtable. -MDNodeOperand::~MDNodeOperand() {} +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"); -void MDNodeOperand::deleted() { - getParent()->replaceOperand(this, nullptr); + ++NextIndex; + assert(NextIndex != 0 && "Unexpected overflow"); } -void MDNodeOperand::allUsesReplacedWith(Value *NV) { - getParent()->replaceOperand(this, NV); +void ReplaceableMetadataImpl::dropRef(void *Ref) { + bool WasErased = UseMap.erase(Ref); + (void)WasErased; + assert(WasErased && "Expected to drop a reference"); } -//===----------------------------------------------------------------------===// -// MDNode implementation. -// - -/// getOperandPtr - Helper function to 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 + 1) + Op; +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 MDNode::replaceOperandWith(unsigned i, Value *Val) { - MDNodeOperand *Op = getOperandPtr(this, i); - replaceOperand(Op, Val); -} +void ReplaceableMetadataImpl::replaceAllUsesWith(Metadata *MD) { + assert(!(MD && isa(MD)) && "Expected non-temp node"); -MDNode::MDNode(LLVMContext &C, ArrayRef Vals, bool isFunctionLocal) -: Value(Type::getMetadataTy(C), Value::MDNodeVal) { - NumOperands = Vals.size(); + if (UseMap.empty()) + return; - if (isFunctionLocal) - setValueSubclassData(getSubclassDataFromValue() | FunctionLocalBit); + // 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) { + 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; + } - // Initialize the operand list, which is co-allocated on the end of the node. - unsigned i = 0; - for (MDNodeOperand *Op = getOperandPtr(this, 0), *E = Op+NumOperands; - Op != E; ++Op, ++i) { - new (Op) MDNodeOperand(Vals[i]); + // Check for MetadataAsValue. + if (Owner.is()) { + Owner.get()->handleChangedMetadata(MD); + continue; + } - // Mark the first MDNodeOperand as being the first in the list of operands. - if (i == 0) - Op->setAsFirstOperand(1); + // 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"); } -/// ~MDNode - Destroy MDNode. -MDNode::~MDNode() { - assert((getSubclassDataFromValue() & DestroyFlag) != 0 && - "Not being destroyed through destroy()?"); - LLVMContextImpl *pImpl = getType()->getContext().pImpl; - if (isNotUniqued()) { - pImpl->NonUniquedMDNodes.erase(this); - } else { - pImpl->MDNodeSet.RemoveNode(this); +void ReplaceableMetadataImpl::resolveAllUses(bool ResolveUsers) { + if (UseMap.empty()) + return; + + if (!ResolveUsers) { + UseMap.clear(); + return; } - // Destroy the operands. - for (MDNodeOperand *Op = getOperandPtr(this, 0), *E = Op+NumOperands; - Op != E; ++Op) - Op->~MDNodeOperand(); -} + // 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; -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; + // Resolve GenericMDNodes that point at this. + auto *OwnerMD = dyn_cast(Owner.get()); + if (!OwnerMD) + continue; + if (OwnerMD->isResolved()) + continue; + OwnerMD->decrementUnresolvedOperands(); + if (!OwnerMD->hasUnresolvedOperands()) + OwnerMD->resolve(); } - if (Argument *A = dyn_cast(V)) +} + +static Function *getLocalFunction(Value *V) { + assert(V && "Expected value"); + if (auto *A = dyn_cast(V)) return A->getParent(); - if (BasicBlock *BB = dyn_cast(V)) + if (BasicBlock *BB = cast(V)->getParent()) return BB->getParent(); - if (MDNode *MD = dyn_cast(V)) - return MD->getFunction(); return nullptr; } -#ifndef NDEBUG -static const Function *assertLocalFunction(const MDNode *N) { - if (!N->isFunctionLocal()) return nullptr; - - // 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; +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(Context, C); else - assert((NewF == nullptr || F == NewF) && - "inconsistent function-local metadata"); + Entry = new LocalAsMetadata(Context, V); } - 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 + return Entry; } -// destroy - Delete this node. Only when there are no uses. -void MDNode::destroy() { - setValueSubclassData(getSubclassDataFromValue() | DestroyFlag); - // Placement delete, then free the memory. - this->~MDNode(); - free(this); +ValueAsMetadata *ValueAsMetadata::getIfExists(Value *V) { + assert(V && "Unexpected null Value"); + return V->getContext().pImpl->ValuesAsMetadata.lookup(V); } -/// isFunctionLocalValue - Return true if this is a value that would require a -/// function-local MDNode. -static bool isFunctionLocalValue(Value *V) { - return isa(V) || isa(V) || isa(V) || - (isa(V) && cast(V)->isFunctionLocal()); -} +void ValueAsMetadata::handleDeletion(Value *V) { + assert(V && "Expected valid value"); -MDNode *MDNode::getMDNode(LLVMContext &Context, ArrayRef Vals, - FunctionLocalness FL, bool Insert) { - LLVMContextImpl *pImpl = Context.pImpl; + auto &Store = V->getType()->getContext().pImpl->ValuesAsMetadata; + auto I = Store.find(V); + if (I == Store.end()) + return; - // Add all the operand pointers. Note that we don't have to add the - // isFunctionLocal bit because that's implied by the operands. - // Note that if the operands are later nulled out, the node will be - // removed from the uniquing map. - FoldingSetNodeID ID; - for (Value *V : Vals) - ID.AddPointer(V); + // 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); - void *InsertPoint; - MDNode *N = pImpl->MDNodeSet.FindNodeOrInsertPos(ID, InsertPoint); + // Delete the metadata. + MD->replaceAllUsesWith(nullptr); + delete MD; +} - if (N || !Insert) - return N; +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; + } - bool isFunctionLocal = false; - switch (FL) { - case FL_Unknown: - for (Value *V : Vals) { - if (!V) continue; - if (isFunctionLocalValue(V)) { - isFunctionLocal = true; - break; - } + // 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; } - break; - case FL_No: - isFunctionLocal = false; - break; - case FL_Yes: - isFunctionLocal = true; - break; + 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; } - // Coallocate space for the node and Operands together, then placement new. - void *Ptr = malloc(sizeof(MDNode) + Vals.size() * sizeof(MDNodeOperand)); - N = new (Ptr) MDNode(Context, Vals, isFunctionLocal); + auto *&Entry = Store[To]; + if (Entry) { + // The target already exists. + MD->replaceAllUsesWith(Entry); + delete MD; + return; + } - // Cache the operand hash. - N->Hash = ID.ComputeHash(); + // 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; +} - // InsertPoint will have been set by the FindNodeOrInsertPos call. - pImpl->MDNodeSet.InsertNode(N, InsertPoint); +//===----------------------------------------------------------------------===// +// MDString implementation. +// - return N; +MDString *MDString::get(LLVMContext &Context, StringRef Str) { + auto &Store = Context.pImpl->MDStringCache; + auto I = Store.find(Str); + if (I != Store.end()) + return &I->second; + + auto *Entry = + StringMapEntry::Create(Str, Store.getAllocator(), MDString()); + bool WasInserted = Store.insert(Entry); + (void)WasInserted; + assert(WasInserted && "Expected entry to be inserted"); + Entry->second.Entry = Entry; + return &Entry->second; } -MDNode *MDNode::get(LLVMContext &Context, ArrayRef Vals) { - return getMDNode(Context, Vals, FL_Unknown); +StringRef MDString::getString() const { + assert(Entry && "Expected to find string map entry"); + return Entry->first(); } -MDNode *MDNode::getWhenValsUnresolved(LLVMContext &Context, - ArrayRef Vals, - bool isFunctionLocal) { - return getMDNode(Context, Vals, isFunctionLocal ? FL_Yes : FL_No); +//===----------------------------------------------------------------------===// +// MDNode implementation. +// + +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; } -MDNode *MDNode::getIfExists(LLVMContext &Context, ArrayRef Vals) { - return getMDNode(Context, Vals, FL_Unknown, false); +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); } -MDNode *MDNode::getTemporary(LLVMContext &Context, ArrayRef Vals) { - MDNode *N = - (MDNode *)malloc(sizeof(MDNode) + Vals.size() * sizeof(MDNodeOperand)); - N = new (N) MDNode(Context, Vals, FL_No); - N->setValueSubclassData(N->getSubclassDataFromValue() | - NotUniquedBit); - LeakDetector::addGarbageObject(N); - return N; +MDNode::MDNode(LLVMContext &Context, unsigned ID, ArrayRef MDs) + : Metadata(ID), Context(Context), NumOperands(MDs.size()), + MDNodeSubclassData(0) { + for (unsigned I = 0, E = MDs.size(); I != E; ++I) + setOperand(I, MDs[I]); } -void MDNode::deleteTemporary(MDNode *N) { - assert(N->use_empty() && "Temporary MDNode has uses!"); - assert(!N->getContext().pImpl->MDNodeSet.RemoveNode(N) && - "Deleting a non-temporary uniqued node!"); - assert(!N->getContext().pImpl->NonUniquedMDNodes.erase(N) && - "Deleting a non-temporary non-uniqued node!"); - assert((N->getSubclassDataFromValue() & NotUniquedBit) && - "Temporary MDNode does not have NotUniquedBit set!"); - assert((N->getSubclassDataFromValue() & DestroyFlag) == 0 && - "Temporary MDNode has DestroyFlag set!"); - LeakDetector::removeGarbageObject(N); - N->destroy(); +bool MDNode::isResolved() const { + if (isa(this)) + return false; + return cast(this)->isResolved(); } -/// getOperand - Return specified operand. -Value *MDNode::getOperand(unsigned i) const { - assert(i < getNumOperands() && "Invalid operand number"); - return *getOperandPtr(const_cast(this), i); +static bool isOperandUnresolved(Metadata *Op) { + if (auto *N = dyn_cast_or_null(Op)) + return !N->isResolved(); + return false; } -void MDNode::Profile(FoldingSetNodeID &ID) const { - // Add all the operand pointers. Note that we don't have to add the - // isFunctionLocal bit because that's implied by the operands. - // Note that if the operands are later nulled out, the node will be - // removed from the uniquing map. - for (unsigned i = 0, e = getNumOperands(); i != e; ++i) - ID.AddPointer(getOperand(i)); +GenericMDNode::GenericMDNode(LLVMContext &C, ArrayRef Vals) + : MDNode(C, GenericMDNodeKind, Vals) { + // Check whether any operands are unresolved, requiring re-uniquing. + for (const auto &Op : operands()) + if (isOperandUnresolved(Op)) + incrementUnresolvedOperands(); + + if (hasUnresolvedOperands()) + ReplaceableUses.reset(new ReplaceableMetadataImpl); } -void MDNode::setIsNotUniqued() { - setValueSubclassData(getSubclassDataFromValue() | NotUniquedBit); - LLVMContextImpl *pImpl = getType()->getContext().pImpl; - pImpl->NonUniquedMDNodes.insert(this); +GenericMDNode::~GenericMDNode() { + LLVMContextImpl *pImpl = getContext().pImpl; + if (isStoredDistinctInContext()) + pImpl->NonUniquedMDNodes.erase(this); + else + pImpl->MDNodeSet.erase(this); + dropAllReferences(); } -// 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 GenericMDNode::resolve() { + assert(!isResolved() && "Expected this to be unresolved"); + + // Move the map, so that this immediately looks resolved. + auto Uses = std::move(ReplaceableUses); + SubclassData32 = 0; + assert(isResolved() && "Expected this to be resolved"); + + // Drop RAUW support. + Uses->resolveAllUses(); +} + +void GenericMDNode::resolveCycles() { + if (isResolved()) + return; + + // Resolve this node immediately. + resolve(); + + // Resolve all operands. + for (const auto &Op : operands()) { + if (!Op) + continue; + assert(!isa(Op) && + "Expected all forward declarations to be resolved"); + if (auto *N = dyn_cast(Op)) + if (!N->isResolved()) + N->resolveCycles(); + } +} + +void MDNode::dropAllReferences() { + for (unsigned I = 0, E = NumOperands; I != E; ++I) + setOperand(I, nullptr); + if (auto *G = dyn_cast(this)) + if (!G->isResolved()) { + G->ReplaceableUses->resolveAllUses(/* ResolveUsers */ false); + G->ReplaceableUses.reset(); } +} + +namespace llvm { +/// \brief Make MDOperand transparent for hashing. +/// +/// This overload of an implementation detail of the hashing library makes +/// MDOperand hash to the same value as a \a Metadata pointer. +/// +/// Note that overloading \a hash_value() as follows: +/// +/// \code +/// size_t hash_value(const MDOperand &X) { return hash_value(X.get()); } +/// \endcode +/// +/// does not cause MDOperand to be transparent. In particular, a bare pointer +/// doesn't get hashed before it's combined, whereas \a MDOperand would. +static const Metadata *get_hashable_data(const MDOperand &X) { return X.get(); } +} + +void GenericMDNode::handleChangedOperand(void *Ref, Metadata *New) { + unsigned Op = static_cast(Ref) - op_begin(); + assert(Op < getNumOperands() && "Expected valid operand"); + + if (isStoredDistinctInContext()) { + assert(isResolved() && "Expected distinct node to be resolved"); + + // This node is not uniqued. Just set the operand and be done with it. + setOperand(Op, New); + return; } - - if (From == To) + if (InRAUW) { + // We just hit a recursion due to RAUW. Set the operand and move on, since + // we're about to be deleted. + // + // FIXME: Can this cycle really happen? + setOperand(Op, New); return; + } - // Update the operand. - Op->set(To); + auto &Store = getContext().pImpl->MDNodeSet; + Store.erase(this); + + Metadata *Old = getOperand(Op); + setOperand(Op, New); + + // Drop uniquing for self-reference cycles or if an operand drops to null. + // + // FIXME: Stop dropping uniquing when an operand drops to null. The original + // motivation was to prevent madness during teardown of LLVMContextImpl, but + // dropAllReferences() fixes that problem in a better way. (It's just here + // now for better staging of semantic changes.) + if (New == this || !New) { + storeDistinctInContext(); + setHash(0); + if (!isResolved()) + resolve(); + 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()) return; + // Re-calculate the hash. + setHash(hash_combine_range(op_begin(), op_end())); +#ifndef NDEBUG + { + SmallVector MDs(op_begin(), op_end()); + unsigned RawHash = hash_combine_range(MDs.begin(), MDs.end()); + assert(getHash() == RawHash && + "Expected hash of MDOperand to equal hash of Metadata*"); + } +#endif - LLVMContextImpl *pImpl = getType()->getContext().pImpl; + // Re-unique the node. + GenericMDNodeInfo::KeyTy Key(this); + auto I = Store.find_as(Key); + if (I == Store.end()) { + Store.insert(this); + + if (!isResolved()) { + // Check if the last unresolved operand has just been resolved; if so, + // resolve this as well. + if (isOperandUnresolved(Old)) + decrementUnresolvedOperands(); + if (isOperandUnresolved(New)) + incrementUnresolvedOperands(); + if (!hasUnresolvedOperands()) + resolve(); + } - // Remove "this" from the context map. FoldingSet doesn't have to reprofile - // this node to remove it, so we don't care what state the operands are in. - pImpl->MDNodeSet.RemoveNode(this); + return; + } - // 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 FoldingSetNodeIDs for MDNodes. - if (!To) { - setIsNotUniqued(); + // Collision. + if (!isResolved()) { + // Still unresolved, so RAUW. + InRAUW = true; + ReplaceableUses->replaceAllUsesWith(*I); + delete this; return; } - // Now that the node is out of the folding set, 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. - FoldingSetNodeID ID; - Profile(ID); - void *InsertPoint; - if (MDNode *N = pImpl->MDNodeSet.FindNodeOrInsertPos(ID, InsertPoint)) { - replaceAllUsesWith(N); - destroy(); + // Store in non-uniqued form if this node has already been resolved. + setHash(0); + storeDistinctInContext(); +} + +MDNode *MDNode::getMDNode(LLVMContext &Context, ArrayRef MDs, + bool Insert) { + auto &Store = Context.pImpl->MDNodeSet; + + GenericMDNodeInfo::KeyTy Key(MDs); + auto I = Store.find_as(Key); + if (I != Store.end()) + return *I; + if (!Insert) + return nullptr; + + // Coallocate space for the node and Operands together, then placement new. + GenericMDNode *N = new (MDs.size()) GenericMDNode(Context, MDs); + N->setHash(Key.Hash); + Store.insert(N); + return N; +} + +MDNodeFwdDecl *MDNode::getTemporary(LLVMContext &Context, + ArrayRef MDs) { + MDNodeFwdDecl *N = new (MDs.size()) MDNodeFwdDecl(Context, MDs); + LeakDetector::addGarbageObject(N); + return N; +} + +void MDNode::deleteTemporary(MDNode *N) { + assert(isa(N) && "Expected forward declaration"); + LeakDetector::removeGarbageObject(N); + delete cast(N); +} + +void MDNode::storeDistinctInContext() { + assert(!IsDistinctInContext && "Expected newly distinct metadata"); + IsDistinctInContext = true; + auto *G = cast(this); + G->setHash(0); + getContext().pImpl->NonUniquedMDNodes.insert(G); +} + +// Replace value from this node's operand list. +void MDNode::replaceOperandWith(unsigned I, Metadata *New) { + if (getOperand(I) == New) + return; + + if (auto *N = dyn_cast(this)) { + N->handleChangedOperand(mutable_begin() + I, New); return; } - // Cache the operand hash. - Hash = ID.ComputeHash(); - // InsertPoint will have been set by the FindNodeOrInsertPos call. - pImpl->MDNodeSet.InsertNode(this, InsertPoint); - - // 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; + assert(isa(this) && "Expected an MDNode"); + setOperand(I, New); +} + +void MDNode::setOperand(unsigned I, Metadata *New) { + assert(I < NumOperands); + if (isStoredDistinctInContext() || isa(this)) + // No need for a callback, this isn't uniqued. + mutable_begin()[I].reset(New, nullptr); + else + mutable_begin()[I].reset(New, this); +} + +/// \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; + } + + return MDNode::get(Context, Ops); +} + +MDNode *MDNode::concatenate(MDNode *A, MDNode *B) { + if (!A) + return B; + if (!B) + return A; + + SmallVector MDs(A->getNumOperands() + B->getNumOperands()); + + unsigned j = 0; + for (unsigned i = 0, ie = A->getNumOperands(); i != ie; ++i) + MDs[j++] = A->getOperand(i); + for (unsigned i = 0, ie = B->getNumOperands(); i != ie; ++i) + MDs[j++] = B->getOperand(i); + + // 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 MDs; + for (unsigned i = 0, ie = A->getNumOperands(); i != ie; ++i) { + Metadata *MD = A->getOperand(i); + for (unsigned j = 0, je = B->getNumOperands(); j != je; ++j) + if (MD == B->getOperand(j)) { + MDs.push_back(MD); break; } - } - if (!isStillFunctionLocal) - setValueSubclassData(getSubclassDataFromValue() & ~FunctionLocalBit); } + + // 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; @@ -425,25 +714,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; @@ -465,31 +756,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; } @@ -497,8 +790,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]; @@ -510,63 +803,55 @@ 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>()) { -} + : Name(N.str()), Parent(nullptr), + Operands(new SmallVector()) {} NamedMDNode::~NamedMDNode() { dropAllReferences(); delete &getNMDOps(Operands); } -/// getNumOperands - Return number of NamedMDNode operands. unsigned NamedMDNode::getNumOperands() const { return (unsigned)getNMDOps(Operands).size(); } -/// getOperand - Return specified operand. MDNode *NamedMDNode::getOperand(unsigned i) const { assert(i < getNumOperands() && "Invalid Operand number!"); - return dyn_cast(&*getNMDOps(Operands)[i]); + auto *N = getNMDOps(Operands)[i].get(); + return cast_or_null(N); } -/// addOperand - Add metadata Operand. -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); } -/// eraseFromParent - Drop all references and remove the node from parent -/// module. void NamedMDNode::eraseFromParent() { getParent()->eraseNamedMetadata(this); } -/// dropAllReferences - Remove all uses and clear node vector. void NamedMDNode::dropAllReferences() { getNMDOps(Operands).clear(); } -/// getName - Return a constant reference to this named metadata's name. StringRef NamedMDNode::getName() const { return StringRef(Name); } @@ -576,7 +861,8 @@ StringRef NamedMDNode::getName() const { // void Instruction::setMetadata(StringRef Kind, MDNode *Node) { - if (!Node && !hasMetadata()) return; + if (!Node && !hasMetadata()) + return; setMetadata(getContext().getMDKindID(Kind), Node); } @@ -615,7 +901,7 @@ void Instruction::dropUnknownMetadata(ArrayRef KnownIDs) { continue; } - Info[I] = Info.back(); + Info[I] = std::move(Info.back()); Info.pop_back(); --E; } @@ -632,7 +918,8 @@ void Instruction::dropUnknownMetadata(ArrayRef KnownIDs) { /// node. This updates/replaces metadata if already present, or removes it if /// Node is null. void Instruction::setMetadata(unsigned KindID, MDNode *Node) { - if (!Node && !hasMetadata()) return; + if (!Node && !hasMetadata()) + return; // Handle 'dbg' as a special case since it is not stored in the hash table. if (KindID == LLVMContext::MD_dbg) { @@ -651,13 +938,14 @@ 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; } @@ -679,7 +967,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; @@ -689,13 +977,15 @@ void Instruction::setMetadata(unsigned KindID, MDNode *Node) { void Instruction::setAAMetadata(const AAMDNodes &N) { setMetadata(LLVMContext::MD_tbaa, N.TBAA); + setMetadata(LLVMContext::MD_alias_scope, N.Scope); + setMetadata(LLVMContext::MD_noalias, N.NoAlias); } 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]; @@ -707,14 +997,14 @@ MDNode *Instruction::getMetadataImpl(unsigned KindID) const { return nullptr; } -void Instruction::getAllMetadataImpl(SmallVectorImpl > &Result) const { +void Instruction::getAllMetadataImpl( + SmallVectorImpl> &Result) const { 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()))); + Result.push_back( + std::make_pair((unsigned)LLVMContext::MD_dbg, DbgLoc.getAsMDNode())); if (!hasMetadataHashEntry()) return; } @@ -725,16 +1015,17 @@ void Instruction::getAllMetadataImpl(SmallVectorImplMetadataStore.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) array_pod_sort(Result.begin(), Result.end()); } -void Instruction:: -getAllMetadataOtherThanDebugLocImpl(SmallVectorImpl > &Result) const { +void Instruction::getAllMetadataOtherThanDebugLocImpl( + SmallVectorImpl> &Result) const { Result.clear(); assert(hasMetadataHashEntry() && getContext().pImpl->MetadataStore.count(this) && @@ -742,7 +1033,9 @@ getAllMetadataOtherThanDebugLocImpl(SmallVectorImplMetadataStore.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,4 +1049,3 @@ void Instruction::clearMetadataHashEntries() { getContext().pImpl->MetadataStore.erase(this); setHasMetadataHashEntry(false); } -