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

diff --git a/docs/ProgrammersManual.html b/docs/ProgrammersManual.html
index ff18d1c9aa8f75aa4438599db3c019b1dfb0bf2a..a9daba3ba93db94047a96da34c07a75d764dbb06 100644 (file)
--- 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.</p>
 

diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h
index 82cf5229e8b3bed7b99ed250bbcc53b2aa258efb..c291406d51a5ae4a1b337f396bfd82e20287992b 100644 (file)
--- a/include/llvm/ADT/DenseMap.h
+++ b/include/llvm/ADT/DenseMap.h
@@ -22,48 +22,39 @@
 namespace llvm {
   
 template<typename T>
-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<typename T>
-struct DenseMapKeyInfo<T*> {
+struct DenseMapInfo<T*> {
   static inline T* getEmptyKey() { return reinterpret_cast<T*>(-1); }
   static inline T* getTombstoneKey() { return reinterpret_cast<T*>(-2); }
   static unsigned getHashValue(const T *PtrVal) {
     return (unsigned(uintptr_t(PtrVal)) >> 4) ^ 
            (unsigned(uintptr_t(PtrVal)) >> 9);
   }
-  static bool isPod() { return true; }
-};
-
-template<typename T>
-struct DenseMapValueInfo {
-  //static bool isPod()
-};
-
-// Provide DenseMapValueInfo for all pointers.
-template<typename T>
-struct DenseMapValueInfo<T*> {
+  static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; }
   static bool isPod() { return true; }
 };
 
 template<typename KeyT, typename ValueT, 
-         typename KeyInfoT = DenseMapKeyInfo<KeyT>,
-         typename ValueInfoT = DenseMapValueInfo<ValueT> >
+         typename KeyInfoT = DenseMapInfo<KeyT>,
+         typename ValueInfoT = DenseMapInfo<ValueT> >
 class DenseMapIterator;
 template<typename KeyT, typename ValueT,
-         typename KeyInfoT = DenseMapKeyInfo<KeyT>,
-         typename ValueInfoT = DenseMapValueInfo<ValueT> >
+         typename KeyInfoT = DenseMapInfo<KeyT>,
+         typename ValueInfoT = DenseMapInfo<ValueT> >
 class DenseMapConstIterator;
 
 template<typename KeyT, typename ValueT,
-         typename KeyInfoT = DenseMapKeyInfo<KeyT>,
-         typename ValueInfoT = DenseMapValueInfo<ValueT> >
+         typename KeyInfoT = DenseMapInfo<KeyT>,
+         typename ValueInfoT = DenseMapInfo<ValueT> >
 class DenseMap {
   typedef std::pair<KeyT, ValueT> 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 40a88eba0a0acf4e2557dec21f40d42cea6ef077..b3e217bf978a39e289be66f73ce8ac976a4ce941 100644 (file)
--- 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 <typename T> struct DenseMapKeyInfo;
+template <typename T> struct DenseMapInfo;
 template <typename T> struct simplify_type;
 template <typename T> struct ilist_traits;
 template<typename NodeTy, typename Traits> class iplist;
@@ -773,13 +773,16 @@ public:
 };
 
 
-template<> struct DenseMapKeyInfo<SDOperand> {
+template<> struct DenseMapInfo<SDOperand> {
   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 cf6a922d23ce444ba09174ff79e78bea5297f516..10f7c9918401e939de2a7d921c1907f4208f06ec 100644 (file)
--- 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 c7f23f51d4b1184dc21d9b9e466616fbbb996dc0..7f402a62b817d751bcbee590a7d6fae7e297b99a 100644 (file)
--- 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 9f7cb003791900661560362ca2f412de74090678..5ab4a60ddcc67646977aa4bb0981de43137ab261 100644 (file)
--- 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<void*>::getHashValue(Val.first) ^
-           DenseMapKeyInfo<void*>::getHashValue(Val.second);
+    return DenseMapInfo<void*>::getHashValue(Val.first) ^
+           DenseMapInfo<void*>::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 7f809e739781fd30807923988583ef9cc57f322a..c6b50a4002d4735e7bedc9038d7d44850f48e759 100644 (file)
--- a/lib/Transforms/Scalar/GVN.cpp
+++ b/lib/Transforms/Scalar/GVN.cpp
@@ -145,7 +145,7 @@ namespace {
 }
 
 namespace llvm {
-template <> struct DenseMapKeyInfo<Expression> {
+template <> struct DenseMapInfo<Expression> {
   static inline Expression getEmptyKey() {
     return Expression(Expression::EMPTY);
   }
@@ -171,6 +171,9 @@ template <> struct DenseMapKeyInfo<Expression> {
     
     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 d362f54b493440902ca448710509a442cdca2dd4..b3d2fe2d5af79409cee7f9c2833d09cd829c1a41 100644 (file)
--- a/lib/Transforms/Scalar/GVNPRE.cpp
+++ b/lib/Transforms/Scalar/GVNPRE.cpp
@@ -155,7 +155,7 @@ namespace {
 }
 
 namespace llvm {
-template <> struct DenseMapKeyInfo<Expression> {
+template <> struct DenseMapInfo<Expression> {
   static inline Expression getEmptyKey() {
     return Expression(Expression::EMPTY);
   }
@@ -181,6 +181,9 @@ template <> struct DenseMapKeyInfo<Expression> {
     
     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 3348971138864568fd29825eea4283462a1d6576..c32457d6704307fbac2c09d58679776bad105b89 100644 (file)
--- 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<std::pair<BasicBlock*, unsigned> > {
-  static inline std::pair<BasicBlock*, unsigned> getEmptyKey() {
-    return std::make_pair((BasicBlock*)-1, ~0U);
+struct DenseMapInfo<std::pair<BasicBlock*, unsigned> > {
+  typedef std::pair<BasicBlock*, unsigned> EltTy;
+  static inline EltTy getEmptyKey() {
+    return EltTy(reinterpret_cast<BasicBlock*>(-1), ~0U);
   }
-  static inline std::pair<BasicBlock*, unsigned> getTombstoneKey() {
-    return std::make_pair((BasicBlock*)-2, 0U);
+  static inline EltTy getTombstoneKey() {
+    return EltTy(reinterpret_cast<BasicBlock*>(-2), 0U);
   }
   static unsigned getHashValue(const std::pair<BasicBlock*, unsigned> &Val) {
-    return DenseMapKeyInfo<void*>::getHashValue(Val.first) + Val.second*2;
+    return DenseMapInfo<void*>::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 2bcd7b68b75f294e5f7a93445faecae84a870831..28b7e45bf55fa2b3db57bfd088d1ffeff7859430 100644 (file)
--- 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<void*>::getHashValue(Key.type) ^ 
+      return DenseMapInfo<void*>::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; }
   };
 }