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.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@266981 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 49 insertions, 0 deletions

diff --git a/unittests/ADT/DenseMapTest.cpp b/unittests/ADT/DenseMapTest.cpp
index caeba457918..db00f8cf8e5 100644
--- a/unittests/ADT/DenseMapTest.cpp
+++ b/unittests/ADT/DenseMapTest.cpp
@@ -496,6 +496,55 @@ TEST(DenseMapCustomTest, StringRefTest) {
   EXPECT_EQ(42, M.lookup(StringRef("a", 0)));
 }
 
+struct CachedHashTest {
+  unsigned Val;
+  unsigned *Counter = nullptr;
+  CachedHashTest(unsigned Val) : Val(Val) {}
+  CachedHashTest(unsigned Val, unsigned *Counter)
+      : Val(Val), Counter(Counter) {}
+};
+}
+namespace llvm {
+template <> struct DenseMapInfo<CachedHashTest> {
+  static CachedHashTest getEmptyKey() { return ~0; }
+  static CachedHashTest getTombstoneKey() { return ~0U - 1; }
+  static unsigned getHashValue(const CachedHashTest &X) {
+    ++*X.Counter;
+    return X.Val;
+  }
+  static bool isEqual(const CachedHashTest &LHS, const CachedHashTest &RHS) {
+    return LHS.Val == RHS.Val;
+  }
+};
+}
+namespace {
+
+TEST(DenseMapCustomTest, CachedHashTest) {
+  unsigned Counter = 0;
+  CachedHashTest Val(0, &Counter);
+  DenseMap<CachedHashTest, int> Map;
+
+  Map[Val] = 0;
+  ASSERT_EQ(1u, Counter);
+
+  Map.reserve(64);
+  ASSERT_EQ(2u, Counter);
+}
+
+// Like above, but now cache the hash.
+TEST(DenseMapCustomTest, CachedHashTest2) {
+  unsigned Counter = 0;
+  CachedHashTest Val(0, &Counter);
+  typedef CachedHash<CachedHashTest> Cached;
+  DenseMap<Cached, int> Map;
+
+  Map[Val] = 0;
+  ASSERT_EQ(1u, Counter);
+
+  Map.reserve(64);
+  ASSERT_EQ(1u, Counter);
+}
+
 // Key traits that allows lookup with either an unsigned or char* key;
 // In the latter case, "a" == 0, "b" == 1 and so on.
 struct TestDenseMapInfo {