Add a CachedHash structure.

A DenseMap doesn't store the hashes, so it needs to recompute them when
the table is resized.

In some applications the hashing cost is noticeable. That is the case
for example in lld for symbol names (StringRef).

This patch adds a templated structure that can wraps any value that can
go in a DenseMap and caches the hash.

llvm-svn: 266981

1 files changed, 30 insertions, 0 deletions

diff --git a/llvm/include/llvm/ADT/DenseMapInfo.h b/llvm/include/llvm/ADT/DenseMapInfo.h
index a844ebcccf5..18c692e0cbc 100644
--- a/llvm/include/llvm/ADT/DenseMapInfo.h
+++ b/llvm/include/llvm/ADT/DenseMapInfo.h
@@ -30,6 +30,36 @@ struct DenseMapInfo {
   //static bool isEqual(const T &LHS, const T &RHS);
 };
 
+template <typename T> struct CachedHash {
+  CachedHash(T Val) : Val(std::move(Val)) {
+    Hash = DenseMapInfo<T>::getHashValue(Val);
+  }
+  CachedHash(T Val, unsigned Hash) : Val(std::move(Val)), Hash(Hash) {}
+  T Val;
+  unsigned Hash;
+};
+
+// Provide DenseMapInfo for all CachedHash<T>.
+template <typename T> struct DenseMapInfo<CachedHash<T>> {
+  static CachedHash<T> getEmptyKey() {
+    T N = DenseMapInfo<T>::getEmptyKey();
+    return {N, 0};
+  }
+  static CachedHash<T> getTombstoneKey() {
+    T N = DenseMapInfo<T>::getTombstoneKey();
+    return {N, 0};
+  }
+  static unsigned getHashValue(CachedHash<T> Val) {
+    assert(!isEqual(Val, getEmptyKey()) && "Cannot hash the empty key!");
+    assert(!isEqual(Val, getTombstoneKey()) &&
+           "Cannot hash the tombstone key!");
+    return Val.Hash;
+  }
+  static bool isEqual(CachedHash<T> A, CachedHash<T> B) {
+    return DenseMapInfo<T>::isEqual(A.Val, B.Val);
+  }
+};
+
 // Provide DenseMapInfo for all pointers.
 template<typename T>
 struct DenseMapInfo<T*> {