From d9489cbb0cf933da9e2154a5336533d6254a5c30 Mon Sep 17 00:00:00 2001 From: Devang Patel Date: Wed, 2 Sep 2009 21:22:09 +0000 Subject: [PATCH] Use CallbackVH, instead of WeakVH, to hold MDNode elements. Use FoldingSetNode to unique MDNodes in a context. Use CallbackVH hooks to update context's MDNodeSet appropriately. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@80839 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Constants.h | 4 +- include/llvm/Metadata.h | 36 +++++++++--- lib/VMCore/Constants.cpp | 4 +- lib/VMCore/ConstantsContext.h | 31 ++++------ lib/VMCore/LLVMContext.cpp | 9 +-- lib/VMCore/LLVMContextImpl.h | 6 +- lib/VMCore/Metadata.cpp | 98 ++++++++++++++++++++++++++++--- unittests/VMCore/MetadataTest.cpp | 2 +- 8 files changed, 145 insertions(+), 45 deletions(-) diff --git a/include/llvm/Constants.h b/include/llvm/Constants.h index fdcc53bc79d..da6fe96a772 100644 --- a/include/llvm/Constants.h +++ b/include/llvm/Constants.h @@ -38,7 +38,7 @@ class VectorType; template struct ConstantCreator; template -struct ConvertConstant; +struct ConvertConstantType; //===----------------------------------------------------------------------===// /// This is the shared class of boolean and integer constants. This class @@ -559,7 +559,7 @@ public: class ConstantExpr : public Constant { friend struct ConstantCreator > >; - friend struct ConvertConstant; + friend struct ConvertConstantType; protected: ConstantExpr(const Type *ty, unsigned Opcode, Use *Ops, unsigned NumOps) diff --git a/include/llvm/Metadata.h b/include/llvm/Metadata.h index b38336b98b0..0844006396d 100644 --- a/include/llvm/Metadata.h +++ b/include/llvm/Metadata.h @@ -19,7 +19,9 @@ #include "llvm/User.h" #include "llvm/Type.h" #include "llvm/OperandTraits.h" +#include "llvm/ADT/FoldingSet.h" #include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/ilist_node.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/ValueHandle.h" @@ -27,8 +29,6 @@ namespace llvm { class Constant; class LLVMContext; -template -struct ConstantCreator; //===----------------------------------------------------------------------===// // MetadataBase - A base class for MDNode, MDString and NamedMDNode. @@ -103,14 +103,32 @@ public: /// MDNode - a tuple of other values. /// These contain a list of the values that represent the metadata. /// MDNode is always unnamed. -class MDNode : public MetadataBase { +class MDNode : public MetadataBase, public FoldingSetNode { MDNode(const MDNode &); // DO NOT IMPLEMENT void *operator new(size_t, unsigned); // DO NOT IMPLEMENT // getNumOperands - Make this only available for private uses. unsigned getNumOperands() { return User::getNumOperands(); } - SmallVector Node; - friend struct ConstantCreator >; + friend class ElementVH; + // Use CallbackVH to hold MDNOde elements. + struct ElementVH : public CallbackVH { + MDNode *Parent; + ElementVH(Value *V, MDNode *P) : CallbackVH(V), Parent(P) {} + ~ElementVH() {} + + virtual void deleted() { + Parent->replaceElement(this->operator Value*(), 0); + } + + virtual void allUsesReplacedWith(Value *NV) { + Parent->replaceElement(this->operator Value*(), NV); + } + }; + // Replace each instance of F from the element list of this node with T. + void replaceElement(Value *F, Value *T); + + SmallVector Node; + protected: explicit MDNode(LLVMContext &C, Value*const* Vals, unsigned NumVals); public: @@ -140,8 +158,8 @@ public: } // Element access - typedef SmallVectorImpl::const_iterator const_elem_iterator; - typedef SmallVectorImpl::iterator elem_iterator; + typedef SmallVectorImpl::const_iterator const_elem_iterator; + typedef SmallVectorImpl::iterator elem_iterator; /// elem_empty - Return true if MDNode is empty. bool elem_empty() const { return Node.empty(); } const_elem_iterator elem_begin() const { return Node.begin(); } @@ -156,6 +174,10 @@ public: return false; } + /// Profile - calculate a unique identifier for this MDNode to collapse + /// duplicates + void Profile(FoldingSetNodeID &ID) const; + virtual void replaceUsesOfWithOnConstant(Value *From, Value *To, Use *U) { llvm_unreachable("This should never be called because MDNodes have no ops"); } diff --git a/lib/VMCore/Constants.cpp b/lib/VMCore/Constants.cpp index fd3266140c1..37efafc9b20 100644 --- a/lib/VMCore/Constants.cpp +++ b/lib/VMCore/Constants.cpp @@ -1880,7 +1880,7 @@ void ConstantArray::replaceUsesOfWithOnConstant(Value *From, Value *To, pImpl->ArrayConstants.InsertOrGetItem(Lookup, Exists); if (Exists) { - Replacement = cast(I->second); + Replacement = I->second; } else { // Okay, the new shape doesn't exist in the system yet. Instead of // creating a new constant array, inserting it, replaceallusesof'ing the @@ -1967,7 +1967,7 @@ void ConstantStruct::replaceUsesOfWithOnConstant(Value *From, Value *To, pImpl->StructConstants.InsertOrGetItem(Lookup, Exists); if (Exists) { - Replacement = cast(I->second); + Replacement = I->second; } else { // Okay, the new shape doesn't exist in the system yet. Instead of // creating a new constant struct, inserting it, replaceallusesof'ing the diff --git a/lib/VMCore/ConstantsContext.h b/lib/VMCore/ConstantsContext.h index f4a2cde5d0f..718470aff42 100644 --- a/lib/VMCore/ConstantsContext.h +++ b/lib/VMCore/ConstantsContext.h @@ -16,7 +16,6 @@ #define LLVM_CONSTANTSCONTEXT_H #include "llvm/Instructions.h" -#include "llvm/Metadata.h" #include "llvm/Operator.h" #include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" @@ -341,7 +340,7 @@ struct ConstantCreator { }; template -struct ConvertConstant { +struct ConvertConstantType { static void convert(ConstantClass *OldC, const TypeClass *NewTy) { llvm_unreachable("This type cannot be converted!"); } @@ -392,7 +391,7 @@ struct ConstantCreator { }; template<> -struct ConvertConstant { +struct ConvertConstantType { static void convert(ConstantExpr *OldC, const Type *NewTy) { Constant *New; switch (OldC->getOpcode()) { @@ -445,14 +444,7 @@ struct ConstantCreator { }; template<> -struct ConstantCreator > { - static MDNode *create(const Type* Ty, const std::vector &V) { - return new MDNode(Ty->getContext(), &V[0], V.size()); - } -}; - -template<> -struct ConvertConstant { +struct ConvertConstantType { static void convert(ConstantVector *OldC, const VectorType *NewTy) { // Make everyone now use a constant of the new type... std::vector C; @@ -466,7 +458,7 @@ struct ConvertConstant { }; template<> -struct ConvertConstant { +struct ConvertConstantType { static void convert(ConstantAggregateZero *OldC, const Type *NewTy) { // Make everyone now use a constant of the new type... Constant *New = ConstantAggregateZero::get(NewTy); @@ -477,7 +469,7 @@ struct ConvertConstant { }; template<> -struct ConvertConstant { +struct ConvertConstantType { static void convert(ConstantArray *OldC, const ArrayType *NewTy) { // Make everyone now use a constant of the new type... std::vector C; @@ -491,7 +483,7 @@ struct ConvertConstant { }; template<> -struct ConvertConstant { +struct ConvertConstantType { static void convert(ConstantStruct *OldC, const StructType *NewTy) { // Make everyone now use a constant of the new type... std::vector C; @@ -514,7 +506,7 @@ struct ConstantCreator { }; template<> -struct ConvertConstant { +struct ConvertConstantType { static void convert(ConstantPointerNull *OldC, const PointerType *NewTy) { // Make everyone now use a constant of the new type... Constant *New = ConstantPointerNull::get(NewTy); @@ -533,7 +525,7 @@ struct ConstantCreator { }; template<> -struct ConvertConstant { +struct ConvertConstantType { static void convert(UndefValue *OldC, const Type *NewTy) { // Make everyone now use a constant of the new type. Constant *New = UndefValue::get(NewTy); @@ -548,8 +540,8 @@ template MapKey; - typedef std::map MapTy; - typedef std::map InverseMapTy; + typedef std::map MapTy; + typedef std::map InverseMapTy; typedef std::map AbstractTypeMapTy; private: /// Map - This is the main map from the element descriptor to the Constants. @@ -767,7 +759,8 @@ public: // leaving will remove() itself, causing the AbstractTypeMapEntry to be // eliminated eventually. do { - ConvertConstant::convert( + ConvertConstantType::convert( static_cast(I->second->second), cast(NewTy)); diff --git a/lib/VMCore/LLVMContext.cpp b/lib/VMCore/LLVMContext.cpp index 1803a9a6666..0ed21fb754e 100644 --- a/lib/VMCore/LLVMContext.cpp +++ b/lib/VMCore/LLVMContext.cpp @@ -13,6 +13,7 @@ //===----------------------------------------------------------------------===// #include "llvm/LLVMContext.h" +#include "llvm/Metadata.h" #include "llvm/Constants.h" #include "llvm/Instruction.h" #include "llvm/Support/ManagedStatic.h" @@ -48,10 +49,10 @@ bool LLVMContext::RemoveDeadMetadata() { bool Changed = false; while (1) { - for (SmallPtrSet::iterator - I = pImpl->MDNodes.begin(), - E = pImpl->MDNodes.end(); I != E; ++I) { - const MDNode *N = cast(*I); + for (FoldingSet::iterator + I = pImpl->MDNodeSet.begin(), + E = pImpl->MDNodeSet.end(); I != E; ++I) { + const MDNode *N = &(*I); if (N->use_empty()) DeadMDNodes.push_back(N); } diff --git a/lib/VMCore/LLVMContextImpl.h b/lib/VMCore/LLVMContextImpl.h index eeafeafd9ee..1ee4ad737e4 100644 --- a/lib/VMCore/LLVMContextImpl.h +++ b/lib/VMCore/LLVMContextImpl.h @@ -19,6 +19,7 @@ #include "LeaksContext.h" #include "TypesContext.h" #include "llvm/LLVMContext.h" +#include "llvm/Metadata.h" #include "llvm/Constants.h" #include "llvm/DerivedTypes.h" #include "llvm/System/Mutex.h" @@ -106,10 +107,12 @@ public: StringMap MDStringCache; + FoldingSet MDNodeSet; + ValueMap AggZeroConstants; SmallPtrSet MDNodes; - + typedef ValueMap, ArrayType, ConstantArray, true /*largekey*/> ArrayConstantsTy; ArrayConstantsTy ArrayConstants; @@ -199,7 +202,6 @@ public: ArrayConstants.freeConstants(); StructConstants.freeConstants(); VectorConstants.freeConstants(); - AggZeroConstants.freeConstants(); NullPtrConstants.freeConstants(); UndefValueConstants.freeConstants(); diff --git a/lib/VMCore/Metadata.cpp b/lib/VMCore/Metadata.cpp index bb8021485f6..bf845eb5422 100644 --- a/lib/VMCore/Metadata.cpp +++ b/lib/VMCore/Metadata.cpp @@ -72,18 +72,37 @@ MDNode::MDNode(LLVMContext &C, Value*const* Vals, unsigned NumVals) // Only record metadata uses. if (MetadataBase *MB = dyn_cast_or_null(Vals[i])) OperandList[NumOperands++] = MB; - Node.push_back(WeakVH(Vals[i])); + Node.push_back(ElementVH(Vals[i], this)); } } +void MDNode::Profile(FoldingSetNodeID &ID) const { + for (const_elem_iterator I = elem_begin(), E = elem_end(); I != E; ++I) + ID.AddPointer(*I); +} + MDNode *MDNode::get(LLVMContext &Context, Value*const* Vals, unsigned NumVals) { - std::vector V; - V.reserve(NumVals); - for (unsigned i = 0; i < NumVals; ++i) - V.push_back(Vals[i]); + LLVMContextImpl *pImpl = Context.pImpl; + FoldingSetNodeID ID; + for (unsigned i = 0; i != NumVals; ++i) + ID.AddPointer(Vals[i]); + + pImpl->ConstantsLock.reader_acquire(); + void *InsertPoint; + MDNode *N = pImpl->MDNodeSet.FindNodeOrInsertPos(ID, InsertPoint); + pImpl->ConstantsLock.reader_release(); - // FIXME : Avoid creating duplicate node. - return new MDNode(Context, &V[0], V.size()); + if (!N) { + sys::SmartScopedWriter Writer(pImpl->ConstantsLock); + N = pImpl->MDNodeSet.FindNodeOrInsertPos(ID, InsertPoint); + if (!N) { + // InsertPoint will have been set by the FindNodeOrInsertPos call. + N = new MDNode(Context, Vals, NumVals); + pImpl->MDNodeSet.InsertNode(N, InsertPoint); + } + } + + return N; } /// dropAllReferences - Remove all uses and clear node vector. @@ -93,10 +112,73 @@ void MDNode::dropAllReferences() { } MDNode::~MDNode() { - getType()->getContext().pImpl->MDNodes.erase(this); + getType()->getContext().pImpl->MDNodeSet.RemoveNode(this); dropAllReferences(); } +// Replace value from this node's element list. +void MDNode::replaceElement(Value *From, Value *To) { + if (From == To || !getType()) + return; + LLVMContext &Context = getType()->getContext(); + LLVMContextImpl *pImpl = Context.pImpl; + + // Find value. This is a linear search, do something if it consumes + // lot of time. It is possible that to have multiple instances of + // From in this MDNode's element list. + SmallVector Indexes; + unsigned Index = 0; + for (SmallVector::iterator I = Node.begin(), + E = Node.end(); I != E; ++I, ++Index) { + Value *V = *I; + if (V && V == From) + Indexes.push_back(Index); + } + + if (Indexes.empty()) + return; + + // Remove "this" from the context map. + { + sys::SmartScopedWriter Writer(pImpl->ConstantsLock); + pImpl->MDNodeSet.RemoveNode(this); + } + + // Replace From element(s) in place. + for (SmallVector::iterator I = Indexes.begin(), E = Indexes.end(); + I != E; ++I) { + unsigned Index = *I; + Node[Index] = ElementVH(To, this); + } + + // Insert updated "this" into the context's folding node set. + // If a node with same element list already exist then before inserting + // updated "this" into the folding node set, replace all uses of existing + // node with updated "this" node. + FoldingSetNodeID ID; + Profile(ID); + pImpl->ConstantsLock.reader_acquire(); + void *InsertPoint; + MDNode *N = pImpl->MDNodeSet.FindNodeOrInsertPos(ID, InsertPoint); + pImpl->ConstantsLock.reader_release(); + + if (N) { + N->replaceAllUsesWith(this); + delete N; + N = 0; + } + + { + sys::SmartScopedWriter Writer(pImpl->ConstantsLock); + N = pImpl->MDNodeSet.FindNodeOrInsertPos(ID, InsertPoint); + if (!N) { + // InsertPoint will have been set by the FindNodeOrInsertPos call. + N = this; + pImpl->MDNodeSet.InsertNode(N, InsertPoint); + } + } +} + //===----------------------------------------------------------------------===// //NamedMDNode implementation // diff --git a/unittests/VMCore/MetadataTest.cpp b/unittests/VMCore/MetadataTest.cpp index f174fb65b81..cdf5a6e6b90 100644 --- a/unittests/VMCore/MetadataTest.cpp +++ b/unittests/VMCore/MetadataTest.cpp @@ -85,7 +85,7 @@ TEST(MDNodeTest, Simple) { MDNode *n2 = MDNode::get(Context, &c1, 1); MDNode *n3 = MDNode::get(Context, &V[0], 3); EXPECT_NE(n1, n2); - // FIXME: Enable uniqueness test. EXPECT_EQ(n1, n3); + EXPECT_EQ(n1, n3); EXPECT_EQ(3u, n1->getNumElements()); EXPECT_EQ(s1, n1->getElement(0)); -- 2.34.1