Fix a compile time regression caused by too small hash tables.

Measure the worst case number of probes for a miss instead of the less
conservative number of probes required for an insertion.

Lower the limit to < 6 probes worst case.

This doubles the size of the ARM and X86 hash tables, other targets are
unaffected. LiveVariables runs 12% faster with this change.

<rdar://problem/9598545>

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

1 files changed, 16 insertions, 3 deletions

diff --git a/utils/TableGen/RegisterInfoEmitter.cpp b/utils/TableGen/RegisterInfoEmitter.cpp
index dcc4b95..6853a0f 100644
--- a/utils/TableGen/RegisterInfoEmitter.cpp
+++ b/utils/TableGen/RegisterInfoEmitter.cpp
@@ -145,7 +145,6 @@ static void generateHashTable(raw_ostream &OS, const char *Name,
     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);
@@ -155,10 +154,24 @@ static void generateHashTable(raw_ostream &OS, const char *Name,
         ProbeAmt += 1;
       }
       HT[Idx] = D;
+    }
+
+    // Now measure the max number of probes for any worst case miss.
+    MaxProbes = 0;
+    unsigned TotalProbes = 0;
+    for (unsigned i = 0, e = HSize; i != e; ++i) {
+      unsigned Idx = i;
+      unsigned ProbeAmt = 1;
+      while (HT[Idx] != Sentinel) {
+        Idx = (Idx + ProbeAmt) & (HSize - 1);
+        ProbeAmt += 1;
+      }
+      TotalProbes += ProbeAmt;
       MaxProbes = std::max(MaxProbes, ProbeAmt);
     }
-    OS << "\n  // Max number of probes: " << MaxProbes;
-  } while (MaxProbes >= 8);
+    OS << "\n  // Max number of probes: " << MaxProbes
+       << format(", avg %.1f", float(TotalProbes)/HSize);
+  } while (MaxProbes >= 6);
 
   // Print the hash table.
   OS << "\n  // Used entries: " << Data.size()