From 76c1b97e4020faace8c95a127f1eab66c278fb58 Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Mon, 17 Sep 2007 18:34:04 +0000 Subject: [PATCH] Merge DenseMapKeyInfo & DenseMapValueInfo into DenseMapInfo Add a new DenseMapInfo::isEqual method to allow clients to redefine the equality predicate used when probing the hash table. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42042 91177308-0d34-0410-b5e6-96231b3b80d8 --- docs/ProgrammersManual.html | 2 +- include/llvm/ADT/DenseMap.h | 41 ++++++++----------- include/llvm/CodeGen/SelectionDAGNodes.h | 7 +++- lib/CodeGen/DwarfWriter.cpp | 1 + lib/CodeGen/RegAllocBigBlock.cpp | 1 + lib/Target/TargetData.cpp | 8 +++- lib/Transforms/Scalar/GVN.cpp | 5 ++- lib/Transforms/Scalar/GVNPRE.cpp | 5 ++- .../Utils/PromoteMemoryToRegister.cpp | 18 ++++---- lib/VMCore/Constants.cpp | 8 +++- 10 files changed, 57 insertions(+), 39 deletions(-) diff --git a/docs/ProgrammersManual.html b/docs/ProgrammersManual.html index ff18d1c9aa8..a9daba3ba93 100644 --- a/docs/ProgrammersManual.html +++ b/docs/ProgrammersManual.html @@ -1225,7 +1225,7 @@ iterators in a densemap are invalidated whenever an insertion occurs, unlike map. Also, because DenseMap allocates space for a large number of key/value pairs (it starts with 64 by default), it will waste a lot of space if your keys or values are large. Finally, you must implement a partial specialization of -DenseMapKeyInfo for the key that you want, if it isn't already supported. This +DenseMapInfo for the key that you want, if it isn't already supported. This is required to tell DenseMap about two special marker values (which can never be inserted into the map) that it needs internally.

diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h index 82cf5229e8b..c291406d51a 100644 --- a/include/llvm/ADT/DenseMap.h +++ b/include/llvm/ADT/DenseMap.h @@ -22,48 +22,39 @@ namespace llvm { template -struct DenseMapKeyInfo { +struct DenseMapInfo { //static inline T getEmptyKey(); //static inline T getTombstoneKey(); //static unsigned getHashValue(const T &Val); + //static bool isEqual(const T &LHS, const T &RHS); //static bool isPod() }; -// Provide DenseMapKeyInfo for all pointers. +// Provide DenseMapInfo for all pointers. template -struct DenseMapKeyInfo { +struct DenseMapInfo { static inline T* getEmptyKey() { return reinterpret_cast(-1); } static inline T* getTombstoneKey() { return reinterpret_cast(-2); } static unsigned getHashValue(const T *PtrVal) { return (unsigned(uintptr_t(PtrVal)) >> 4) ^ (unsigned(uintptr_t(PtrVal)) >> 9); } - static bool isPod() { return true; } -}; - -template -struct DenseMapValueInfo { - //static bool isPod() -}; - -// Provide DenseMapValueInfo for all pointers. -template -struct DenseMapValueInfo { + static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; } static bool isPod() { return true; } }; template, - typename ValueInfoT = DenseMapValueInfo > + typename KeyInfoT = DenseMapInfo, + typename ValueInfoT = DenseMapInfo > class DenseMapIterator; template, - typename ValueInfoT = DenseMapValueInfo > + typename KeyInfoT = DenseMapInfo, + typename ValueInfoT = DenseMapInfo > class DenseMapConstIterator; template, - typename ValueInfoT = DenseMapValueInfo > + typename KeyInfoT = DenseMapInfo, + typename ValueInfoT = DenseMapInfo > class DenseMap { typedef std::pair BucketT; unsigned NumBuckets; @@ -280,14 +271,14 @@ private: while (1) { BucketT *ThisBucket = BucketsPtr + (BucketNo & (NumBuckets-1)); // Found Val's bucket? If so, return it. - if (ThisBucket->first == Val) { + if (KeyInfoT::isEqual(ThisBucket->first, Val)) { FoundBucket = ThisBucket; return true; } // If we found an empty bucket, the key doesn't exist in the set. // Insert it and return the default value. - if (ThisBucket->first == EmptyKey) { + if (KeyInfoT::isEqual(ThisBucket->first, EmptyKey)) { // If we've already seen a tombstone while probing, fill it in instead // of the empty bucket we eventually probed to. if (FoundTombstone) ThisBucket = FoundTombstone; @@ -297,7 +288,7 @@ private: // If this is a tombstone, remember it. If Val ends up not in the map, we // prefer to return it than something that would require more probing. - if (ThisBucket->first == TombstoneKey && !FoundTombstone) + if (KeyInfoT::isEqual(ThisBucket->first, TombstoneKey) && !FoundTombstone) FoundTombstone = ThisBucket; // Remember the first tombstone found. // Otherwise, it's a hash collision or a tombstone, continue quadratic @@ -425,7 +416,9 @@ private: const KeyT Empty = KeyInfoT::getEmptyKey(); const KeyT Tombstone = KeyInfoT::getTombstoneKey(); - while (Ptr != End && (Ptr->first == Empty || Ptr->first == Tombstone)) + while (Ptr != End && + (KeyInfoT::isEqual(Ptr->first, Empty) || + KeyInfoT::isEqual(Ptr->first, Tombstone))) ++Ptr; } }; diff --git a/include/llvm/CodeGen/SelectionDAGNodes.h b/include/llvm/CodeGen/SelectionDAGNodes.h index 40a88eba0a0..b3e217bf978 100644 --- a/include/llvm/CodeGen/SelectionDAGNodes.h +++ b/include/llvm/CodeGen/SelectionDAGNodes.h @@ -35,7 +35,7 @@ class GlobalValue; class MachineBasicBlock; class MachineConstantPoolValue; class SDNode; -template struct DenseMapKeyInfo; +template struct DenseMapInfo; template struct simplify_type; template struct ilist_traits; template class iplist; @@ -773,13 +773,16 @@ public: }; -template<> struct DenseMapKeyInfo { +template<> struct DenseMapInfo { static inline SDOperand getEmptyKey() { return SDOperand((SDNode*)-1, -1U); } static inline SDOperand getTombstoneKey() { return SDOperand((SDNode*)-1, 0);} static unsigned getHashValue(const SDOperand &Val) { return (unsigned)((uintptr_t)Val.Val >> 4) ^ (unsigned)((uintptr_t)Val.Val >> 9) + Val.ResNo; } + static bool isEqual(const SDOperand &LHS, const SDOperand &RHS) { + return LHS == RHS; + } static bool isPod() { return true; } }; diff --git a/lib/CodeGen/DwarfWriter.cpp b/lib/CodeGen/DwarfWriter.cpp index cf6a922d23c..10f7c991840 100644 --- a/lib/CodeGen/DwarfWriter.cpp +++ b/lib/CodeGen/DwarfWriter.cpp @@ -2942,6 +2942,7 @@ private: static inline unsigned getEmptyKey() { return -1U; } static inline unsigned getTombstoneKey() { return -2U; } static unsigned getHashValue(const unsigned &Key) { return Key; } + static bool isEqual(unsigned LHS, unsigned RHS) { return LHS == RHS; } static bool isPod() { return true; } }; diff --git a/lib/CodeGen/RegAllocBigBlock.cpp b/lib/CodeGen/RegAllocBigBlock.cpp index c7f23f51d4b..7f402a62b81 100644 --- a/lib/CodeGen/RegAllocBigBlock.cpp +++ b/lib/CodeGen/RegAllocBigBlock.cpp @@ -63,6 +63,7 @@ namespace { struct VRegKeyInfo { static inline unsigned getEmptyKey() { return -1U; } static inline unsigned getTombstoneKey() { return -2U; } + static bool isEqual(unsigned LHS, unsigned RHS) { return LHS == RHS; } static unsigned getHashValue(const unsigned &Key) { return Key; } }; diff --git a/lib/Target/TargetData.cpp b/lib/Target/TargetData.cpp index 9f7cb003791..5ab4a60ddcc 100644 --- a/lib/Target/TargetData.cpp +++ b/lib/Target/TargetData.cpp @@ -316,9 +316,13 @@ struct DenseMapLayoutKeyInfo { return LayoutKey((TargetData*)(intptr_t)-1, 0); } static unsigned getHashValue(const LayoutKey &Val) { - return DenseMapKeyInfo::getHashValue(Val.first) ^ - DenseMapKeyInfo::getHashValue(Val.second); + return DenseMapInfo::getHashValue(Val.first) ^ + DenseMapInfo::getHashValue(Val.second); } + static bool isEqual(const LayoutKey &LHS, const LayoutKey &RHS) { + return LHS == RHS; + } + static bool isPod() { return true; } }; diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp index 7f809e73978..c6b50a4002d 100644 --- a/lib/Transforms/Scalar/GVN.cpp +++ b/lib/Transforms/Scalar/GVN.cpp @@ -145,7 +145,7 @@ namespace { } namespace llvm { -template <> struct DenseMapKeyInfo { +template <> struct DenseMapInfo { static inline Expression getEmptyKey() { return Expression(Expression::EMPTY); } @@ -171,6 +171,9 @@ template <> struct DenseMapKeyInfo { return hash; } + static bool isEqual(const Expression &LHS, const Expression &RHS) { + return LHS == RHS; + } static bool isPod() { return true; } }; } diff --git a/lib/Transforms/Scalar/GVNPRE.cpp b/lib/Transforms/Scalar/GVNPRE.cpp index d362f54b493..b3d2fe2d5af 100644 --- a/lib/Transforms/Scalar/GVNPRE.cpp +++ b/lib/Transforms/Scalar/GVNPRE.cpp @@ -155,7 +155,7 @@ namespace { } namespace llvm { -template <> struct DenseMapKeyInfo { +template <> struct DenseMapInfo { static inline Expression getEmptyKey() { return Expression(Expression::EMPTY); } @@ -181,6 +181,9 @@ template <> struct DenseMapKeyInfo { return hash; } + static bool isEqual(const Expression &LHS, const Expression &RHS) { + return LHS == RHS; + } static bool isPod() { return true; } }; } diff --git a/lib/Transforms/Utils/PromoteMemoryToRegister.cpp b/lib/Transforms/Utils/PromoteMemoryToRegister.cpp index 33489711388..c32457d6704 100644 --- a/lib/Transforms/Utils/PromoteMemoryToRegister.cpp +++ b/lib/Transforms/Utils/PromoteMemoryToRegister.cpp @@ -39,18 +39,22 @@ STATISTIC(NumSingleStore, "Number of alloca's promoted with a single store"); STATISTIC(NumDeadAlloca, "Number of dead alloca's removed"); STATISTIC(NumPHIInsert, "Number of PHI nodes inserted"); -// Provide DenseMapKeyInfo for all pointers. +// Provide DenseMapInfo for all pointers. namespace llvm { template<> -struct DenseMapKeyInfo > { - static inline std::pair getEmptyKey() { - return std::make_pair((BasicBlock*)-1, ~0U); +struct DenseMapInfo > { + typedef std::pair EltTy; + static inline EltTy getEmptyKey() { + return EltTy(reinterpret_cast(-1), ~0U); } - static inline std::pair getTombstoneKey() { - return std::make_pair((BasicBlock*)-2, 0U); + static inline EltTy getTombstoneKey() { + return EltTy(reinterpret_cast(-2), 0U); } static unsigned getHashValue(const std::pair &Val) { - return DenseMapKeyInfo::getHashValue(Val.first) + Val.second*2; + return DenseMapInfo::getHashValue(Val.first) + Val.second*2; + } + static bool isEqual(const EltTy &LHS, const EltTy &RHS) { + return LHS == RHS; } static bool isPod() { return true; } }; diff --git a/lib/VMCore/Constants.cpp b/lib/VMCore/Constants.cpp index 2bcd7b68b75..28b7e45bf55 100644 --- a/lib/VMCore/Constants.cpp +++ b/lib/VMCore/Constants.cpp @@ -203,9 +203,12 @@ namespace { static inline KeyTy getEmptyKey() { return KeyTy(APInt(1,0), 0); } static inline KeyTy getTombstoneKey() { return KeyTy(APInt(1,1), 0); } static unsigned getHashValue(const KeyTy &Key) { - return DenseMapKeyInfo::getHashValue(Key.type) ^ + return DenseMapInfo::getHashValue(Key.type) ^ Key.val.getHashValue(); } + static bool isEqual(const KeyTy &LHS, const KeyTy &RHS) { + return LHS == RHS; + } static bool isPod() { return false; } }; } @@ -293,6 +296,9 @@ namespace { static unsigned getHashValue(const KeyTy &Key) { return Key.val.getHashValue(); } + static bool isEqual(const KeyTy &LHS, const KeyTy &RHS) { + return LHS == RHS; + } static bool isPod() { return false; } }; } -- 2.34.1