From: Talin Date: Sun, 5 Feb 2012 20:54:10 +0000 (+0000) Subject: Efficient Constant Uniquing. X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=commitdiff_plain;h=2cb395eae71dacda49ca3fe758618fc3e0701659 Efficient Constant Uniquing. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@149848 91177308-0d34-0410-b5e6-96231b3b80d8 --- diff --git a/include/llvm/Constants.h b/include/llvm/Constants.h index a4723d37f0e..0abe17d365d 100644 --- a/include/llvm/Constants.h +++ b/include/llvm/Constants.h @@ -39,6 +39,8 @@ class SequentialType; template struct ConstantCreator; template +struct ConstantArrayCreator; +template struct ConvertConstantType; //===----------------------------------------------------------------------===// @@ -343,8 +345,7 @@ public: /// ConstantArray - Constant Array Declarations /// class ConstantArray : public Constant { - friend struct ConstantCreator >; + friend struct ConstantArrayCreator; ConstantArray(const ConstantArray &); // DO NOT IMPLEMENT protected: ConstantArray(ArrayType *T, ArrayRef Val); @@ -383,8 +384,7 @@ DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ConstantArray, Constant) // ConstantStruct - Constant Struct Declarations // class ConstantStruct : public Constant { - friend struct ConstantCreator >; + friend struct ConstantArrayCreator; ConstantStruct(const ConstantStruct &); // DO NOT IMPLEMENT protected: ConstantStruct(StructType *T, ArrayRef Val); @@ -444,8 +444,7 @@ DEFINE_TRANSPARENT_OPERAND_ACCESSORS(ConstantStruct, Constant) /// ConstantVector - Constant Vector Declarations /// class ConstantVector : public Constant { - friend struct ConstantCreator >; + friend struct ConstantArrayCreator; ConstantVector(const ConstantVector &); // DO NOT IMPLEMENT protected: ConstantVector(VectorType *T, ArrayRef Val); diff --git a/lib/VMCore/Constants.cpp b/lib/VMCore/Constants.cpp index 7d423c04a61..bffe8591090 100644 --- a/lib/VMCore/Constants.cpp +++ b/lib/VMCore/Constants.cpp @@ -2388,11 +2388,9 @@ void ConstantArray::replaceUsesOfWithOnConstant(Value *From, Value *To, LLVMContextImpl *pImpl = getType()->getContext().pImpl; - std::pair Lookup; - Lookup.first.first = cast(getType()); - Lookup.second = this; - - std::vector &Values = Lookup.first.second; + SmallVector Values; + LLVMContextImpl::ArrayConstantsTy::LookupKey Lookup; + Lookup.first = cast(getType()); Values.reserve(getNumOperands()); // Build replacement array. // Fill values with the modified operands of the constant array. Also, @@ -2408,7 +2406,7 @@ void ConstantArray::replaceUsesOfWithOnConstant(Value *From, Value *To, ++NumUpdated; } Values.push_back(Val); - AllSame = Val == ToC; + AllSame &= Val == ToC; } Constant *Replacement = 0; @@ -2418,18 +2416,18 @@ void ConstantArray::replaceUsesOfWithOnConstant(Value *From, Value *To, Replacement = UndefValue::get(getType()); } else { // Check to see if we have this array type already. - bool Exists; + Lookup.second = makeArrayRef(Values); LLVMContextImpl::ArrayConstantsTy::MapTy::iterator I = - pImpl->ArrayConstants.InsertOrGetItem(Lookup, Exists); + pImpl->ArrayConstants.find(Lookup); - if (Exists) { - Replacement = I->second; + if (I != pImpl->ArrayConstants.map_end()) { + Replacement = I->first; } else { // Okay, the new shape doesn't exist in the system yet. Instead of // creating a new constant array, inserting it, replaceallusesof'ing the // old with the new, then deleting the old... just update the current one // in place! - pImpl->ArrayConstants.MoveConstantToNewSlot(this, I); + pImpl->ArrayConstants.remove(this); // Update to the new value. Optimize for the case when we have a single // operand that we're changing, but handle bulk updates efficiently. @@ -2443,6 +2441,7 @@ void ConstantArray::replaceUsesOfWithOnConstant(Value *From, Value *To, if (getOperand(i) == From) setOperand(i, ToC); } + pImpl->ArrayConstants.insert(this); return; } } @@ -2465,13 +2464,11 @@ void ConstantStruct::replaceUsesOfWithOnConstant(Value *From, Value *To, unsigned OperandToUpdate = U-OperandList; assert(getOperand(OperandToUpdate) == From && "ReplaceAllUsesWith broken!"); - std::pair Lookup; - Lookup.first.first = cast(getType()); - Lookup.second = this; - std::vector &Values = Lookup.first.second; + SmallVector Values; + LLVMContextImpl::StructConstantsTy::LookupKey Lookup; + Lookup.first = cast(getType()); Values.reserve(getNumOperands()); // Build replacement struct. - // Fill values with the modified operands of the constant struct. Also, // compute whether this turns into an all-zeros struct. bool isAllZeros = false; @@ -2505,21 +2502,22 @@ void ConstantStruct::replaceUsesOfWithOnConstant(Value *From, Value *To, Replacement = UndefValue::get(getType()); } else { // Check to see if we have this struct type already. - bool Exists; + Lookup.second = makeArrayRef(Values); LLVMContextImpl::StructConstantsTy::MapTy::iterator I = - pImpl->StructConstants.InsertOrGetItem(Lookup, Exists); + pImpl->StructConstants.find(Lookup); - if (Exists) { - Replacement = I->second; + if (I != pImpl->StructConstants.map_end()) { + Replacement = I->first; } else { // Okay, the new shape doesn't exist in the system yet. Instead of // creating a new constant struct, inserting it, replaceallusesof'ing the // old with the new, then deleting the old... just update the current one // in place! - pImpl->StructConstants.MoveConstantToNewSlot(this, I); + pImpl->StructConstants.remove(this); // Update to the new value. setOperand(OperandToUpdate, ToC); + pImpl->StructConstants.insert(this); return; } } diff --git a/lib/VMCore/ConstantsContext.h b/lib/VMCore/ConstantsContext.h index b7726944a22..a7277f67364 100644 --- a/lib/VMCore/ConstantsContext.h +++ b/lib/VMCore/ConstantsContext.h @@ -15,6 +15,7 @@ #ifndef LLVM_CONSTANTSCONTEXT_H #define LLVM_CONSTANTSCONTEXT_H +#include "llvm/ADT/DenseMap.h" #include "llvm/InlineAsm.h" #include "llvm/Instructions.h" #include "llvm/Operator.h" @@ -408,6 +409,13 @@ struct ConstantCreator { } }; +template +struct ConstantArrayCreator { + static ConstantClass *create(TypeClass *Ty, ArrayRef V) { + return new(V.size()) ConstantClass(Ty, V); + } +}; + template struct ConstantKeyData { typedef void ValType; @@ -477,44 +485,6 @@ struct ConstantKeyData { } }; - -template<> -struct ConstantKeyData { - typedef std::vector ValType; - static ValType getValType(ConstantVector *CP) { - std::vector Elements; - Elements.reserve(CP->getNumOperands()); - for (unsigned i = 0, e = CP->getNumOperands(); i != e; ++i) - Elements.push_back(CP->getOperand(i)); - return Elements; - } -}; - -template<> -struct ConstantKeyData { - typedef std::vector ValType; - static ValType getValType(ConstantArray *CA) { - std::vector Elements; - Elements.reserve(CA->getNumOperands()); - for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i) - Elements.push_back(cast(CA->getOperand(i))); - return Elements; - } -}; - -template<> -struct ConstantKeyData { - typedef std::vector ValType; - static ValType getValType(ConstantStruct *CS) { - std::vector Elements; - Elements.reserve(CS->getNumOperands()); - for (unsigned i = 0, e = CS->getNumOperands(); i != e; ++i) - Elements.push_back(cast(CS->getOperand(i))); - return Elements; - } -}; - - template<> struct ConstantCreator { static InlineAsm *create(PointerType *Ty, const InlineAsmKeyType &Key) { @@ -668,6 +638,159 @@ public: } }; +// Unique map for aggregate constants +template +class ConstantAggrUniqueMap { +public: + typedef ArrayRef Operands; + typedef std::pair LookupKey; +private: + struct MapInfo { + typedef DenseMapInfo ConstantClassInfo; + typedef DenseMapInfo ConstantInfo; + typedef DenseMapInfo TypeClassInfo; + static inline ConstantClass* getEmptyKey() { + return ConstantClassInfo::getEmptyKey(); + } + static inline ConstantClass* getTombstoneKey() { + return ConstantClassInfo::getTombstoneKey(); + } + static unsigned getHashValue(const ConstantClass *CP) { + // This is adapted from SuperFastHash by Paul Hsieh. + unsigned Hash = TypeClassInfo::getHashValue(CP->getType()); + for (unsigned I = 0, E = CP->getNumOperands(); I < E; ++I) { + unsigned Data = ConstantInfo::getHashValue(CP->getOperand(I)); + Hash += Data & 0xFFFF; + unsigned Tmp = ((Data >> 16) << 11) ^ Hash; + Hash = (Hash << 16) ^ Tmp; + Hash += Hash >> 11; + } + + // Force "avalanching" of final 127 bits. + Hash ^= Hash << 3; + Hash += Hash >> 5; + Hash ^= Hash << 4; + Hash += Hash >> 17; + Hash ^= Hash << 25; + Hash += Hash >> 6; + return Hash; + } + static bool isEqual(const ConstantClass *LHS, const ConstantClass *RHS) { + return LHS == RHS; + } + static unsigned getHashValue(const LookupKey &Val) { + // This is adapted from SuperFastHash by Paul Hsieh. + unsigned Hash = TypeClassInfo::getHashValue(Val.first); + for (Operands::const_iterator + I = Val.second.begin(), E = Val.second.end(); I != E; ++I) { + unsigned Data = ConstantInfo::getHashValue(*I); + Hash += Data & 0xFFFF; + unsigned Tmp = ((Data >> 16) << 11) ^ Hash; + Hash = (Hash << 16) ^ Tmp; + Hash += Hash >> 11; + } + + // Force "avalanching" of final 127 bits. + Hash ^= Hash << 3; + Hash += Hash >> 5; + Hash ^= Hash << 4; + Hash += Hash >> 17; + Hash ^= Hash << 25; + Hash += Hash >> 6; + return Hash; + } + static bool isEqual(const LookupKey &LHS, const ConstantClass *RHS) { + if (RHS == getEmptyKey() || RHS == getTombstoneKey()) + return false; + if (LHS.first != RHS->getType() + || LHS.second.size() != RHS->getNumOperands()) + return false; + for (unsigned I = 0, E = RHS->getNumOperands(); I < E; ++I) { + if (LHS.second[I] != RHS->getOperand(I)) + return false; + } + return true; + } + }; +public: + typedef DenseMap MapTy; + +private: + /// Map - This is the main map from the element descriptor to the Constants. + /// This is the primary way we avoid creating two of the same shape + /// constant. + MapTy Map; + +public: + typename MapTy::iterator map_begin() { return Map.begin(); } + typename MapTy::iterator map_end() { return Map.end(); } + + void freeConstants() { + for (typename MapTy::iterator I=Map.begin(), E=Map.end(); + I != E; ++I) { + // Asserts that use_empty(). + delete I->first; + } + } + +private: + typename MapTy::iterator findExistingElement(ConstantClass *CP) { + return Map.find(CP); + } + + ConstantClass *Create(TypeClass *Ty, Operands V, typename MapTy::iterator I) { + ConstantClass* Result = + ConstantArrayCreator::create(Ty, V); + + assert(Result->getType() == Ty && "Type specified is not correct!"); + Map[Result] = '\0'; + + return Result; + } +public: + + /// getOrCreate - Return the specified constant from the map, creating it if + /// necessary. + ConstantClass *getOrCreate(TypeClass *Ty, Operands V) { + LookupKey Lookup(Ty, V); + ConstantClass* Result = 0; + + typename MapTy::iterator I = Map.find_as(Lookup); + // Is it in the map? + if (I != Map.end()) + Result = I->first; + + if (!Result) { + // If no preexisting value, create one now... + Result = Create(Ty, V, I); + } + + return Result; + } + + /// Find the constant by lookup key. + typename MapTy::iterator find(LookupKey Lookup) { + return Map.find_as(Lookup); + } + + /// Insert the constant into its proper slot. + void insert(ConstantClass *CP) { + Map[CP] = '\0'; + } + + /// Remove this constant from the map + void remove(ConstantClass *CP) { + typename MapTy::iterator I = findExistingElement(CP); + assert(I != Map.end() && "Constant not found in constant table!"); + assert(I->first == CP && "Didn't find correct element?"); + Map.erase(I); + } + + void dump() const { + DEBUG(dbgs() << "Constant.cpp: ConstantUniqueMap\n"); + } +}; + } #endif diff --git a/lib/VMCore/LLVMContextImpl.cpp b/lib/VMCore/LLVMContextImpl.cpp index 15c5c246772..6279bb823db 100644 --- a/lib/VMCore/LLVMContextImpl.cpp +++ b/lib/VMCore/LLVMContextImpl.cpp @@ -48,6 +48,16 @@ struct DropReferences { P.second->dropAllReferences(); } }; + +// Temporary - drops pair.first instead of second. +struct DropFirst { + // Takes the value_type of a ConstantUniqueMap's internal map, whose 'second' + // is a Constant*. + template + void operator()(const PairT &P) { + P.first->dropAllReferences(); + } +}; } LLVMContextImpl::~LLVMContextImpl() { @@ -63,11 +73,11 @@ LLVMContextImpl::~LLVMContextImpl() { std::for_each(ExprConstants.map_begin(), ExprConstants.map_end(), DropReferences()); std::for_each(ArrayConstants.map_begin(), ArrayConstants.map_end(), - DropReferences()); + DropFirst()); std::for_each(StructConstants.map_begin(), StructConstants.map_end(), - DropReferences()); + DropFirst()); std::for_each(VectorConstants.map_begin(), VectorConstants.map_end(), - DropReferences()); + DropFirst()); ExprConstants.freeConstants(); ArrayConstants.freeConstants(); StructConstants.freeConstants(); diff --git a/lib/VMCore/LLVMContextImpl.h b/lib/VMCore/LLVMContextImpl.h index ca37ffa9faf..a27afc08b9f 100644 --- a/lib/VMCore/LLVMContextImpl.h +++ b/lib/VMCore/LLVMContextImpl.h @@ -140,16 +140,13 @@ public: DenseMap CAZConstants; - typedef ConstantUniqueMap, ArrayRef, - ArrayType, ConstantArray, true /*largekey*/> ArrayConstantsTy; + typedef ConstantAggrUniqueMap ArrayConstantsTy; ArrayConstantsTy ArrayConstants; - typedef ConstantUniqueMap, ArrayRef, - StructType, ConstantStruct, true /*largekey*/> StructConstantsTy; + typedef ConstantAggrUniqueMap StructConstantsTy; StructConstantsTy StructConstants; - typedef ConstantUniqueMap, ArrayRef, - VectorType, ConstantVector> VectorConstantsTy; + typedef ConstantAggrUniqueMap VectorConstantsTy; VectorConstantsTy VectorConstants; DenseMap CPNConstants;