From b95fd2d5fd4818a601dd1df05f38863e3ca5c920 Mon Sep 17 00:00:00 2001
From: Jakob Stoklund Olesen <stoklund@2pi.dk>
Date: Sun, 12 Jun 2011 07:04:32 +0000
Subject: [PATCH] Tweak hash function and compress hash tables.

Make the hash tables as small as possible while ensuring that all
lookups can be done in less than 8 probes.

Cut the aliases hash table in half by only storing a < b pairs - it
is a symmetric relation.

Use larger multipliers on the initial hash function to ensure that it
properly covers the whole table, and to resolve some clustering in the
very regular ARM register bank.

This reduces the size of most of these tables by 4x - 8x. For instance,
the ARM tables shrink from 48 KB to 8 KB.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@132888 91177308-0d34-0410-b5e6-96231b3b80d8
---
 include/llvm/Target/TargetRegisterInfo.h | 21 ++++++------
 utils/TableGen/RegisterInfoEmitter.cpp   | 43 +++++++++++++-----------
 2 files changed, 35 insertions(+), 29 deletions(-)

diff --git a/include/llvm/Target/TargetRegisterInfo.h b/include/llvm/Target/TargetRegisterInfo.h
index 10f668c57fc..f85cdeb0496 100644
--- a/include/llvm/Target/TargetRegisterInfo.h
+++ b/include/llvm/Target/TargetRegisterInfo.h
@@ -471,19 +471,21 @@ public:
     if (regA == regB)
       return true;
 
+    if (regA > regB)
+      std::swap(regA, regB);
+
     if (isVirtualRegister(regA) || isVirtualRegister(regB))
       return false;
 
     // regA and regB are distinct physical registers. Do they alias?
-    size_t index = (regA + regB * 37) & (AliasesHashSize-1);
-    unsigned ProbeAmt = 0;
-    while (AliasesHash[index*2] != 0 &&
-           AliasesHash[index*2+1] != 0) {
+    size_t index = (regA * 11 + regB * 97) & (AliasesHashSize-1);
+    unsigned ProbeAmt = 1;
+    while (AliasesHash[index*2] != 0 && AliasesHash[index*2+1] != 0) {
       if (AliasesHash[index*2] == regA && AliasesHash[index*2+1] == regB)
         return true;
 
       index = (index + ProbeAmt) & (AliasesHashSize-1);
-      ProbeAmt += 2;
+      ProbeAmt += 1;
     }
 
     return false;
@@ -493,15 +495,14 @@ public:
   ///
   bool isSubRegister(unsigned regA, unsigned regB) const {
     // SubregHash is a simple quadratically probed hash table.
-    size_t index = (regA + regB * 37) & (SubregHashSize-1);
-    unsigned ProbeAmt = 2;
-    while (SubregHash[index*2] != 0 &&
-           SubregHash[index*2+1] != 0) {
+    size_t index = (regA * 11 + regB * 97) & (SubregHashSize-1);
+    unsigned ProbeAmt = 1;
+    while (SubregHash[index*2] != 0 && SubregHash[index*2+1] != 0) {
       if (SubregHash[index*2] == regA && SubregHash[index*2+1] == regB)
         return true;
 
       index = (index + ProbeAmt) & (SubregHashSize-1);
-      ProbeAmt += 2;
+      ProbeAmt += 1;
     }
 
     return false;
diff --git a/utils/TableGen/RegisterInfoEmitter.cpp b/utils/TableGen/RegisterInfoEmitter.cpp
index 7ccee8b5333..dcc4b95d2f3 100644
--- a/utils/TableGen/RegisterInfoEmitter.cpp
+++ b/utils/TableGen/RegisterInfoEmitter.cpp
@@ -137,27 +137,31 @@ static void generateHashTable(raw_ostream &OS, const char *Name,
   unsigned HSize = Data.size();
   UUVector HT;
 
-  // Hashtable size must be a power of two.
-  HSize = 2 * NextPowerOf2(2 * HSize);
-  HT.assign(HSize, Sentinel);
-
-  // Insert all entries.
-  unsigned MaxProbes = 0;
-  for (unsigned i = 0, e = Data.size(); i != e; ++i) {
-    UUPair D = Data[i];
-    unsigned Idx = (D.first + D.second * 37) & (HSize - 1);
-    unsigned ProbeAmt = 2;
-    while (HT[Idx] != Sentinel) {
-      Idx = (Idx + ProbeAmt) & (HSize - 1);
-      ProbeAmt += 2;
+  // Grow the hash table until all entries can be found in less than 8 probes.
+  unsigned MaxProbes;
+  do {
+    // Hashtable size must be a power of two.
+    HSize = NextPowerOf2(HSize);
+    HT.assign(HSize, Sentinel);
+
+    // Insert all entries.
+    MaxProbes = 0;
+    for (unsigned i = 0, e = Data.size(); i != e; ++i) {
+      UUPair D = Data[i];
+      unsigned Idx = (D.first * 11 + D.second * 97) & (HSize - 1);
+      unsigned ProbeAmt = 1;
+      while (HT[Idx] != Sentinel) {
+        Idx = (Idx + ProbeAmt) & (HSize - 1);
+        ProbeAmt += 1;
+      }
+      HT[Idx] = D;
+      MaxProbes = std::max(MaxProbes, ProbeAmt);
     }
-    HT[Idx] = D;
-    MaxProbes = std::max(MaxProbes, ProbeAmt/2);
-  }
+    OS << "\n  // Max number of probes: " << MaxProbes;
+  } while (MaxProbes >= 8);
 
   // Print the hash table.
-  OS << "\n\n  // Max number of probes: " << MaxProbes
-     << "\n  // Used entries: " << Data.size()
+  OS << "\n  // Used entries: " << Data.size()
      << "\n  const unsigned " << Name << "Size = " << HSize << ';'
      << "\n  const unsigned " << Name << "[] = {\n";
 
@@ -441,13 +445,14 @@ void RegisterInfoEmitter::run(raw_ostream &OS) {
 
   // Print the AliasHashTable, a simple quadratically probed
   // hash table for determining if a register aliases another register.
+  // Since the overlaps() relation is symmetric, only store a < b pairs.
   HTData.clear();
   for (unsigned i = 0, e = Regs.size(); i != e; ++i) {
     unsigned RegNo = Regs[i].EnumValue;
     const CodeGenRegister::Set &O = Overlaps[&Regs[i]];
     for (CodeGenRegister::Set::const_iterator I = O.begin(), E = O.end();
          I != E; ++I)
-      if (*I != &Regs[i])
+      if (RegNo < (*I)->EnumValue)
         HTData.push_back(UUPair(RegNo, (*I)->EnumValue));
   }
   generateHashTable(OS, "AliasesHashTable", HTData);
-- 
2.34.1