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

1 files changed, 11 insertions, 10 deletions

diff --git a/include/llvm/Target/TargetRegisterInfo.h b/include/llvm/Target/TargetRegisterInfo.h
index 10f668c57f..f85cdeb049 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;