-//===-- Metadata.cpp - Implement Metadata classes -------------------------===//
+//===- Metadata.cpp - Implement Metadata classes --------------------------===//
//
// The LLVM Compiler Infrastructure
//
#include "llvm/IR/Metadata.h"
#include "LLVMContextImpl.h"
+#include "MetadataImpl.h"
#include "SymbolTableListTraitsImpl.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/STLExtras.h"
#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/Module.h"
Metadata *MD) {
MD = canonicalizeMetadataForValue(Context, MD);
auto &Store = Context.pImpl->MetadataAsValues;
- auto I = Store.find(MD);
- return I == Store.end() ? nullptr : I->second;
+ return Store.lookup(MD);
}
void MetadataAsValue::handleChangedMetadata(Metadata *MD) {
if (Owner.is<MetadataAsValue *>())
continue;
- // Resolve UniquableMDNodes that point at this.
- auto *OwnerMD = dyn_cast<UniquableMDNode>(Owner.get<Metadata *>());
+ // Resolve MDNodes that point at this.
+ auto *OwnerMD = dyn_cast<MDNode>(Owner.get<Metadata *>());
if (!OwnerMD)
continue;
if (OwnerMD->isResolved())
}
MDNode::MDNode(LLVMContext &Context, unsigned ID, StorageType Storage,
- ArrayRef<Metadata *> MDs)
- : Metadata(ID, Storage), Context(Context), NumOperands(MDs.size()),
- MDNodeSubclassData(0) {
- for (unsigned I = 0, E = MDs.size(); I != E; ++I)
- setOperand(I, MDs[I]);
+ ArrayRef<Metadata *> Ops1, ArrayRef<Metadata *> 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;
+
+ if (isUniqued())
+ // Check whether any operands are unresolved, requiring re-uniquing. If
+ // not, don't support RAUW.
+ if (!countUnresolvedOperands())
+ return;
- if (isTemporary())
- this->Context.makeReplaceable(
- make_unique<ReplaceableMetadataImpl>(Context));
+ this->Context.makeReplaceable(make_unique<ReplaceableMetadataImpl>(Context));
+}
+
+TempMDNode MDNode::clone() const {
+ switch (getMetadataID()) {
+ default:
+ llvm_unreachable("Invalid MDNode subclass");
+#define HANDLE_MDNODE_LEAF(CLASS) \
+ case CLASS##Kind: \
+ return cast<CLASS>(this)->cloneImpl();
+#include "llvm/IR/Metadata.def"
+ }
}
static bool isOperandUnresolved(Metadata *Op) {
return false;
}
-UniquableMDNode::UniquableMDNode(LLVMContext &C, unsigned ID,
- StorageType Storage, ArrayRef<Metadata *> Vals)
- : MDNode(C, ID, Storage, Vals) {
- if (!isUniqued())
- return;
-
- // Check whether any operands are unresolved, requiring re-uniquing.
- unsigned NumUnresolved = countUnresolvedOperands();
- if (!NumUnresolved)
- return;
-
- this->Context.makeReplaceable(make_unique<ReplaceableMetadataImpl>(C));
- SubclassData32 = NumUnresolved;
-}
-
-unsigned UniquableMDNode::countUnresolvedOperands() const {
- unsigned NumUnresolved = 0;
- for (const auto &Op : operands())
- NumUnresolved += unsigned(isOperandUnresolved(Op));
+unsigned MDNode::countUnresolvedOperands() {
+ assert(NumUnresolved == 0 && "Expected unresolved ops to be uncounted");
+ NumUnresolved = std::count_if(op_begin(), op_end(), isOperandUnresolved);
return NumUnresolved;
}
-void UniquableMDNode::makeUniqued() {
+void MDNode::makeUniqued() {
assert(isTemporary() && "Expected this to be temporary");
assert(!isResolved() && "Expected this to be unresolved");
+ // Enable uniquing callbacks.
+ for (auto &Op : mutable_operands())
+ Op.reset(Op.get(), this);
+
// Make this 'uniqued'.
Storage = Uniqued;
- if (unsigned NumUnresolved = countUnresolvedOperands())
- SubclassData32 = NumUnresolved;
- else
+ if (!countUnresolvedOperands())
resolve();
assert(isUniqued() && "Expected this to be uniqued");
}
-void UniquableMDNode::makeDistinct() {
+void MDNode::makeDistinct() {
assert(isTemporary() && "Expected this to be temporary");
assert(!isResolved() && "Expected this to be unresolved");
assert(isResolved() && "Expected this to be resolved");
}
-void UniquableMDNode::resolve() {
+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();
- SubclassData32 = 0;
+ NumUnresolved = 0;
assert(isResolved() && "Expected this to be resolved");
// Drop RAUW support.
Uses->resolveAllUses();
}
-void UniquableMDNode::resolveAfterOperandChange(Metadata *Old, Metadata *New) {
- assert(SubclassData32 != 0 && "Expected unresolved operands");
+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!
- ++SubclassData32;
+ ++NumUnresolved;
} else if (!isOperandUnresolved(New))
decrementUnresolvedOperandCount();
}
-void UniquableMDNode::decrementUnresolvedOperandCount() {
- if (!--SubclassData32)
+void MDNode::decrementUnresolvedOperandCount() {
+ if (!--NumUnresolved)
// Last unresolved operand has just been resolved.
resolve();
}
-void UniquableMDNode::resolveCycles() {
+void MDNode::resolveCycles() {
if (isResolved())
return;
// Resolve all operands.
for (const auto &Op : operands()) {
- auto *N = dyn_cast_or_null<UniquableMDNode>(Op);
+ auto *N = dyn_cast_or_null<MDNode>(Op);
if (!N)
continue;
}
}
+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();
+}
+
+MDNode *MDNode::replaceWithUniquedImpl() {
+ // Try to uniquify in place.
+ MDNode *UniquedNode = uniquify();
+
+ if (UniquedNode == this) {
+ makeUniqued();
+ return this;
+ }
+
+ // Collision, so RAUW instead.
+ replaceAllUsesWith(UniquedNode);
+ deleteAsSubclass();
+ return UniquedNode;
+}
+
+MDNode *MDNode::replaceWithDistinctImpl() {
+ makeDistinct();
+ return this;
+}
+
void MDTuple::recalculateHash() {
setHash(MDTupleInfo::KeyTy::calculateHash(this));
}
void MDNode::dropAllReferences() {
for (unsigned I = 0, E = NumOperands; I != E; ++I)
setOperand(I, nullptr);
- if (auto *N = dyn_cast<UniquableMDNode>(this))
- if (!N->isResolved()) {
- N->Context.getReplaceableUses()->resolveAllUses(/* ResolveUsers */ false);
- (void)N->Context.takeReplaceableUses();
- }
+ if (!isResolved()) {
+ Context.getReplaceableUses()->resolveAllUses(/* ResolveUsers */ false);
+ (void)Context.takeReplaceableUses();
+ }
}
-void UniquableMDNode::handleChangedOperand(void *Ref, Metadata *New) {
+void MDNode::handleChangedOperand(void *Ref, Metadata *New) {
unsigned Op = static_cast<MDOperand *>(Ref) - op_begin();
assert(Op < getNumOperands() && "Expected valid operand");
storeDistinctInContext();
}
-void UniquableMDNode::deleteAsSubclass() {
+void MDNode::deleteAsSubclass() {
switch (getMetadataID()) {
default:
- llvm_unreachable("Invalid subclass of UniquableMDNode");
-#define HANDLE_UNIQUABLE_LEAF(CLASS) \
+ llvm_unreachable("Invalid subclass of MDNode");
+#define HANDLE_MDNODE_LEAF(CLASS) \
case CLASS##Kind: \
delete cast<CLASS>(this); \
break;
}
}
-template <class T, class InfoT>
-static T *getUniqued(DenseSet<T *, InfoT> &Store,
- const typename InfoT::KeyTy &Key) {
- auto I = Store.find_as(Key);
- return I == Store.end() ? nullptr : *I;
-}
-
template <class T, class InfoT>
static T *uniquifyImpl(T *N, DenseSet<T *, InfoT> &Store) {
if (T *U = getUniqued(Store, N))
return N;
}
-UniquableMDNode *UniquableMDNode::uniquify() {
- // Recalculate hash, if necessary.
- switch (getMetadataID()) {
- default:
- break;
- case MDTupleKind:
- cast<MDTuple>(this)->recalculateHash();
- break;
- }
+template <class NodeTy> struct MDNode::HasCachedHash {
+ typedef char Yes[1];
+ typedef char No[2];
+ template <class U, U Val> struct SFINAE {};
+
+ template <class U>
+ static Yes &check(SFINAE<void (U::*)(unsigned), &U::setHash> *);
+ template <class U> static No &check(...);
+
+ static const bool value = sizeof(check<NodeTy>(nullptr)) == sizeof(Yes);
+};
+
+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 UniquableMDNode");
-#define HANDLE_UNIQUABLE_LEAF(CLASS) \
- case CLASS##Kind: \
- return uniquifyImpl(cast<CLASS>(this), getContext().pImpl->CLASS##s);
+ llvm_unreachable("Invalid subclass of MDNode");
+#define HANDLE_MDNODE_LEAF(CLASS) \
+ case CLASS##Kind: { \
+ CLASS *SubclassThis = cast<CLASS>(this); \
+ std::integral_constant<bool, HasCachedHash<CLASS>::value> \
+ ShouldRecalculateHash; \
+ dispatchRecalculateHash(SubclassThis, ShouldRecalculateHash); \
+ return uniquifyImpl(SubclassThis, getContext().pImpl->CLASS##s); \
+ }
#include "llvm/IR/Metadata.def"
}
}
-void UniquableMDNode::eraseFromStore() {
+void MDNode::eraseFromStore() {
switch (getMetadataID()) {
default:
- llvm_unreachable("Invalid subclass of UniquableMDNode");
-#define HANDLE_UNIQUABLE_LEAF(CLASS) \
+ llvm_unreachable("Invalid subclass of MDNode");
+#define HANDLE_MDNODE_LEAF(CLASS) \
case CLASS##Kind: \
getContext().pImpl->CLASS##s.erase(cast<CLASS>(this)); \
break;
}
}
-template <class T, class StoreT>
-T *UniquableMDNode::storeImpl(T *N, StorageType Storage, StoreT &Store) {
- switch (Storage) {
- case Uniqued:
- Store.insert(N);
- break;
- case Distinct:
- N->storeDistinctInContext();
- break;
- case Temporary:
- break;
- }
- return N;
-}
-
MDTuple *MDTuple::getImpl(LLVMContext &Context, ArrayRef<Metadata *> MDs,
StorageType Storage, bool ShouldCreate) {
unsigned Hash = 0;
Storage, Context.pImpl->MDTuples);
}
-MDLocation::MDLocation(LLVMContext &C, StorageType Storage, unsigned Line,
- unsigned Column, ArrayRef<Metadata *> MDs)
- : UniquableMDNode(C, MDLocationKind, Storage, MDs) {
- assert((MDs.size() == 1 || MDs.size() == 2) &&
- "Expected a scope and optional inlined-at");
-
- // Set line and column.
- assert(Line < (1u << 24) && "Expected 24-bit line");
- assert(Column < (1u << 16) && "Expected 16-bit column");
-
- MDNodeSubclassData = Line;
- SubclassData16 = Column;
-}
-
-static void adjustLine(unsigned &Line) {
- // Set to unknown on overflow. Still use 24 bits for now.
- if (Line >= (1u << 24))
- Line = 0;
-}
-
-static void adjustColumn(unsigned &Column) {
- // Set to unknown on overflow. We only have 16 bits to play with here.
- if (Column >= (1u << 16))
- Column = 0;
-}
-
-MDLocation *MDLocation::getImpl(LLVMContext &Context, unsigned Line,
- unsigned Column, Metadata *Scope,
- Metadata *InlinedAt, StorageType Storage,
- bool ShouldCreate) {
- // Fixup line/column.
- adjustLine(Line);
- adjustColumn(Column);
-
- if (Storage == Uniqued) {
- if (auto *N = getUniqued(
- Context.pImpl->MDLocations,
- MDLocationInfo::KeyTy(Line, Column, Scope, InlinedAt)))
- return N;
- if (!ShouldCreate)
- return nullptr;
- } else {
- assert(ShouldCreate && "Expected non-uniqued nodes to always be created");
- }
-
- SmallVector<Metadata *, 2> Ops;
- Ops.push_back(Scope);
- if (InlinedAt)
- Ops.push_back(InlinedAt);
- return storeImpl(new (Ops.size())
- MDLocation(Context, Storage, Line, Column, Ops),
- Storage, Context.pImpl->MDLocations);
-}
-
void MDNode::deleteTemporary(MDNode *N) {
assert(N->isTemporary() && "Expected temporary node");
- cast<UniquableMDNode>(N)->deleteAsSubclass();
+ N->replaceAllUsesWith(nullptr);
+ N->deleteAsSubclass();
}
-void UniquableMDNode::storeDistinctInContext() {
+void MDNode::storeDistinctInContext() {
assert(isResolved() && "Expected resolved nodes");
Storage = Distinct;
- if (auto *T = dyn_cast<MDTuple>(this))
- T->setHash(0);
+
+ // Reset the hash.
+ switch (getMetadataID()) {
+ default:
+ llvm_unreachable("Invalid subclass of MDNode");
+#define HANDLE_MDNODE_LEAF(CLASS) \
+ case CLASS##Kind: { \
+ std::integral_constant<bool, HasCachedHash<CLASS>::value> ShouldResetHash; \
+ dispatchResetHash(cast<CLASS>(this), ShouldResetHash); \
+ break; \
+ }
+#include "llvm/IR/Metadata.def"
+ }
+
getContext().pImpl->DistinctMDNodes.insert(this);
}
return;
}
- cast<UniquableMDNode>(this)->handleChangedOperand(mutable_begin() + I, New);
+ handleChangedOperand(mutable_begin() + I, New);
}
void MDNode::setOperand(unsigned I, Metadata *New) {
if (!B)
return A;
- SmallVector<Metadata *, 4> 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);
+ SmallVector<Metadata *, 4> MDs;
+ MDs.reserve(A->getNumOperands() + B->getNumOperands());
+ MDs.append(A->op_begin(), A->op_end());
+ MDs.append(B->op_begin(), B->op_end());
// FIXME: This preserves long-standing behaviour, but is it really the right
// behaviour? Or was that an unintended side-effect of node uniquing?
return nullptr;
SmallVector<Metadata *, 4> 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;
- }
- }
+ 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;
+
+ SmallVector<Metadata *, 4> 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?
if (!hasMetadataHashEntry())
return; // Nothing to remove!
- DenseMap<const Instruction *, LLVMContextImpl::MDMapTy> &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;
- }
-
- Info[I] = std::move(Info.back());
- Info.pop_back();
- --E;
- }
- assert(E == Info.size());
+ auto &Info = InstructionMetadata[this];
+ Info.erase(std::remove_if(
+ Info.begin(), Info.end(),
+ [&KnownSet](const std::pair<unsigned, TrackingMDNodeRef> &I) {
+ return !KnownSet.count(I.first);
+ }),
+ Info.end());
- if (E == 0) {
+ if (Info.empty()) {
// Drop our entry at the store.
- MetadataStore.erase(this);
+ InstructionMetadata.erase(this);
setHasMetadataHashEntry(false);
}
}
// 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()) {
// 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;
}
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)
Result.clear();
// Handle 'dbg' as a special case since it is not stored in the hash table.
- if (!DbgLoc.isUnknown()) {
+ 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.reserve(Result.size() + Info.size());
SmallVectorImpl<std::pair<unsigned, MDNode *>> &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.reserve(Result.size() + Info.size());
for (auto &I : Info)
/// this instruction.
void Instruction::clearMetadataHashEntries() {
assert(hasMetadataHashEntry() && "Caller should check");
- getContext().pImpl->MetadataStore.erase(this);
+ getContext().pImpl->InstructionMetadata.erase(this);
setHasMetadataHashEntry(false);
}