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

10 files changed, 57 insertions, 39 deletions

diff --git a/docs/ProgrammersManual.html b/docs/ProgrammersManual.html
index ff18d1c9aa..a9daba3ba9 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.</p>
 
diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h
index 82cf5229e8..c291406d51 100644
--- 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 40a88eba0a..b3e217bf97 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 <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 cf6a922d23..10f7c99184 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 c7f23f51d4..7f402a62b8 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 9f7cb00379..5ab4a60ddc 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<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 7f809e7397..c6b50a4002 100644
--- 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 d362f54b49..b3d2fe2d5a 100644
--- 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 3348971138..c32457d670 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<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 2bcd7b68b7..28b7e45bf5 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<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; }
   };
 }