Speed up addRegisterDead by adding more fast checks before performing the expensive

subregister query, and by increasing the size of the subregister hashtable so
that there are fewer collisions.


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

1 files changed, 9 insertions, 3 deletions

diff --git a/utils/TableGen/RegisterInfoEmitter.cpp b/utils/TableGen/RegisterInfoEmitter.cpp
index 2870c8038b..d514bf7deb 100644
--- a/utils/TableGen/RegisterInfoEmitter.cpp
+++ b/utils/TableGen/RegisterInfoEmitter.cpp
@@ -473,10 +473,12 @@ void RegisterInfoEmitter::run(std::ostream &OS) {
     NumSubRegs += RegisterSubRegs[Regs[i].TheDef].size();
   }
   
-  unsigned SubregHashTableSize = NextPowerOf2(2 * NumSubRegs);
+  unsigned SubregHashTableSize = 2 * NextPowerOf2(2 * NumSubRegs);
   unsigned* SubregHashTable = new unsigned[2 * SubregHashTableSize];
   std::fill(SubregHashTable, SubregHashTable + 2 * SubregHashTableSize, ~0U);
   
+  unsigned hashMisses = 0;
+  
   for (unsigned i = 0, e = Regs.size(); i != e; ++i) {
     Record* R = Regs[i].TheDef;
     for (std::set<Record*>::iterator I = RegisterSubRegs[R].begin(),
@@ -491,6 +493,8 @@ void RegisterInfoEmitter::run(std::ostream &OS) {
              SubregHashTable[index*2+1] != ~0U) {
         index = (index + ProbeAmt) & (SubregHashTableSize-1);
         ProbeAmt += 2;
+        
+        hashMisses++;
       }
       
       SubregHashTable[index*2] = i;
@@ -498,10 +502,12 @@ void RegisterInfoEmitter::run(std::ostream &OS) {
     }
   }
   
+  OS << "\n\n  // Number of hash collisions: " << hashMisses << "\n";
+  
   if (SubregHashTableSize) {
     std::string Namespace = Regs[0].TheDef->getValueAsString("Namespace");
     
-    OS << "\n\n  const unsigned SubregHashTable[] = { ";
+    OS << "  const unsigned SubregHashTable[] = { ";
     for (unsigned i = 0; i < SubregHashTableSize - 1; ++i) {
       if (i != 0)
         // Insert spaces for nice formatting.
@@ -527,7 +533,7 @@ void RegisterInfoEmitter::run(std::ostream &OS) {
     OS << "  const unsigned SubregHashTableSize = "
        << SubregHashTableSize << ";\n";
   } else {
-    OS << "\n\n  const unsigned SubregHashTable[] = { ~0U, ~0U };\n"
+    OS << "  const unsigned SubregHashTable[] = { ~0U, ~0U };\n"
        << "  const unsigned SubregHashTableSize = 1;\n";
   }