diff options
-rw-r--r-- | include/llvm/Constants.h | 4 | ||||
-rw-r--r-- | include/llvm/Metadata.h | 36 | ||||
-rw-r--r-- | lib/VMCore/Constants.cpp | 4 | ||||
-rw-r--r-- | lib/VMCore/ConstantsContext.h | 31 | ||||
-rw-r--r-- | lib/VMCore/LLVMContext.cpp | 9 | ||||
-rw-r--r-- | lib/VMCore/LLVMContextImpl.h | 6 | ||||
-rw-r--r-- | lib/VMCore/Metadata.cpp | 98 | ||||
-rw-r--r-- | 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 fdcc53b..da6fe96 100644 --- a/include/llvm/Constants.h +++ b/include/llvm/Constants.h @@ -38,7 +38,7 @@ class VectorType; template<class ConstantClass, class TypeClass, class ValType> struct ConstantCreator; template<class ConstantClass, class TypeClass> -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<ConstantExpr,Type, std::pair<unsigned, std::vector<Constant*> > >; - friend struct ConvertConstant<ConstantExpr, Type>; + friend struct ConvertConstantType<ConstantExpr, Type>; protected: ConstantExpr(const Type *ty, unsigned Opcode, Use *Ops, unsigned NumOps) diff --git a/include/llvm/Metadata.h b/include/llvm/Metadata.h index b38336b..0844006 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<class ConstantClass, class TypeClass, class ValType> -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<WeakVH, 4> Node; - friend struct ConstantCreator<MDNode, Type, std::vector<Value*> >; + 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<ElementVH, 4> Node; + protected: explicit MDNode(LLVMContext &C, Value*const* Vals, unsigned NumVals); public: @@ -140,8 +158,8 @@ public: } // Element access - typedef SmallVectorImpl<WeakVH>::const_iterator const_elem_iterator; - typedef SmallVectorImpl<WeakVH>::iterator elem_iterator; + typedef SmallVectorImpl<ElementVH>::const_iterator const_elem_iterator; + typedef SmallVectorImpl<ElementVH>::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 fd32661..37efafc 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<Constant>(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<Constant>(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 f4a2cde..718470a 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<class ConstantClass, class TypeClass> -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<ConstantExpr, Type, ExprMapKeyType> { }; template<> -struct ConvertConstant<ConstantExpr, Type> { +struct ConvertConstantType<ConstantExpr, Type> { static void convert(ConstantExpr *OldC, const Type *NewTy) { Constant *New; switch (OldC->getOpcode()) { @@ -445,14 +444,7 @@ struct ConstantCreator<ConstantAggregateZero, Type, ValType> { }; template<> -struct ConstantCreator<MDNode, Type, std::vector<Value*> > { - static MDNode *create(const Type* Ty, const std::vector<Value*> &V) { - return new MDNode(Ty->getContext(), &V[0], V.size()); - } -}; - -template<> -struct ConvertConstant<ConstantVector, VectorType> { +struct ConvertConstantType<ConstantVector, VectorType> { static void convert(ConstantVector *OldC, const VectorType *NewTy) { // Make everyone now use a constant of the new type... std::vector<Constant*> C; @@ -466,7 +458,7 @@ struct ConvertConstant<ConstantVector, VectorType> { }; template<> -struct ConvertConstant<ConstantAggregateZero, Type> { +struct ConvertConstantType<ConstantAggregateZero, Type> { 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<ConstantAggregateZero, Type> { }; template<> -struct ConvertConstant<ConstantArray, ArrayType> { +struct ConvertConstantType<ConstantArray, ArrayType> { static void convert(ConstantArray *OldC, const ArrayType *NewTy) { // Make everyone now use a constant of the new type... std::vector<Constant*> C; @@ -491,7 +483,7 @@ struct ConvertConstant<ConstantArray, ArrayType> { }; template<> -struct ConvertConstant<ConstantStruct, StructType> { +struct ConvertConstantType<ConstantStruct, StructType> { static void convert(ConstantStruct *OldC, const StructType *NewTy) { // Make everyone now use a constant of the new type... std::vector<Constant*> C; @@ -514,7 +506,7 @@ struct ConstantCreator<ConstantPointerNull, PointerType, ValType> { }; template<> -struct ConvertConstant<ConstantPointerNull, PointerType> { +struct ConvertConstantType<ConstantPointerNull, PointerType> { 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<UndefValue, Type, ValType> { }; template<> -struct ConvertConstant<UndefValue, Type> { +struct ConvertConstantType<UndefValue, Type> { 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<class ValType, class TypeClass, class ConstantClass, class ValueMap : public AbstractTypeUser { public: typedef std::pair<const Type*, ValType> MapKey; - typedef std::map<MapKey, Value *> MapTy; - typedef std::map<Value*, typename MapTy::iterator> InverseMapTy; + typedef std::map<MapKey, Constant *> MapTy; + typedef std::map<Constant*, typename MapTy::iterator> InverseMapTy; typedef std::map<const Type*, typename MapTy::iterator> 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<ConstantClass, TypeClass>::convert( + ConvertConstantType<ConstantClass, + TypeClass>::convert( static_cast<ConstantClass *>(I->second->second), cast<TypeClass>(NewTy)); diff --git a/lib/VMCore/LLVMContext.cpp b/lib/VMCore/LLVMContext.cpp index 1803a9a..0ed21fb 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<const MDNode *, 8>::iterator - I = pImpl->MDNodes.begin(), - E = pImpl->MDNodes.end(); I != E; ++I) { - const MDNode *N = cast<MDNode>(*I); + for (FoldingSet<MDNode>::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 eeafeaf..1ee4ad7 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<MDString*> MDStringCache; + FoldingSet<MDNode> MDNodeSet; + ValueMap<char, Type, ConstantAggregateZero> AggZeroConstants; SmallPtrSet<const MDNode *, 8> MDNodes; - + typedef ValueMap<std::vector<Constant*>, 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 bb80214..bf845eb 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<MetadataBase>(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<Value*> 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<true> 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<unsigned, 4> Indexes; + unsigned Index = 0; + for (SmallVector<ElementVH, 4>::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<true> Writer(pImpl->ConstantsLock); + pImpl->MDNodeSet.RemoveNode(this); + } + + // Replace From element(s) in place. + for (SmallVector<unsigned, 4>::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<true> 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 f174fb6..cdf5a6e 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)); |