Replace the dynamically computed std::set lookup method for subregisters with a hashtable-based

version that is computed by tblgen at the time LLVM is compiled.


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

3 files changed, 84 insertions, 13 deletions

diff --git a/include/llvm/Target/TargetRegisterInfo.h b/include/llvm/Target/TargetRegisterInfo.h
index 858b064538..b385559178 100644
--- a/include/llvm/Target/TargetRegisterInfo.h
+++ b/include/llvm/Target/TargetRegisterInfo.h
@@ -274,6 +274,9 @@ public:
 /// descriptor.
 ///
 class TargetRegisterInfo {
+protected:
+  unsigned* SubregHash;
+  unsigned SubregHashSize;
 public:
   typedef const TargetRegisterClass * const * regclass_iterator;
 private:
@@ -283,7 +286,6 @@ private:
   regclass_iterator RegClassBegin, RegClassEnd;   // List of regclasses
 
   int CallFrameSetupOpcode, CallFrameDestroyOpcode;
-  std::set<std::pair<unsigned, unsigned> > Subregs;
 protected:
   TargetRegisterInfo(const TargetRegisterDesc *D, unsigned NR,
                      regclass_iterator RegClassBegin,
@@ -410,7 +412,19 @@ public:
   /// isSubRegister - Returns true if regB is a sub-register of regA.
   ///
   bool isSubRegister(unsigned regA, unsigned regB) const {
-    return Subregs.count(std::make_pair(regA, regB));
+    // SubregHash is a simple quadratically probed hash table.
+    size_t index = (regA + regB * 37) % SubregHashSize;
+    unsigned ProbeAmt = 2;
+    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;
+      ProbeAmt += 2;
+    }
+    
+    return false;
   }
 
   /// isSuperRegister - Returns true if regB is a super-register of regA.
diff --git a/lib/Target/TargetRegisterInfo.cpp b/lib/Target/TargetRegisterInfo.cpp
index e69496f4b2..3f44a0cb5a 100644
--- a/lib/Target/TargetRegisterInfo.cpp
+++ b/lib/Target/TargetRegisterInfo.cpp
@@ -29,16 +29,6 @@ TargetRegisterInfo::TargetRegisterInfo(const TargetRegisterDesc *D, unsigned NR,
 
   CallFrameSetupOpcode   = CFSO;
   CallFrameDestroyOpcode = CFDO;
-  
-  for (unsigned i = 0; i < NumRegs; ++i) {
-    const TargetRegisterDesc* CurrReg = Desc + i;
-    
-    // Initialize the Subregs set, which stores pairs (a, b) where
-    // b is a subreg of a.
-    if (CurrReg->SubRegs)
-      for (const unsigned* CurrSR = CurrReg->SubRegs; *CurrSR; ++CurrSR)
-        Subregs.insert(std::make_pair(i, *CurrSR));
-  }
 }
 
 TargetRegisterInfo::~TargetRegisterInfo() {}
diff --git a/utils/TableGen/RegisterInfoEmitter.cpp b/utils/TableGen/RegisterInfoEmitter.cpp
index 42dccb8eb1..64e1dfee0f 100644
--- a/utils/TableGen/RegisterInfoEmitter.cpp
+++ b/utils/TableGen/RegisterInfoEmitter.cpp
@@ -462,6 +462,70 @@ void RegisterInfoEmitter::run(std::ostream &OS) {
                      RegisterAliases);
     }
   }
+  
+  // Print the SubregHashTable, a simple quadratically probed
+  // hash table for determining if a register is a subregister
+  // of another register.
+  unsigned SubregHashTableSize = NextPowerOf2(2 * Regs.size());
+  unsigned* SubregHashTable =
+                  (unsigned*)malloc(2 * SubregHashTableSize * sizeof(unsigned));
+  for (unsigned i = 0; i < SubregHashTableSize * 2; ++i)
+    SubregHashTable[i] = ~0U;
+  
+  std::map<Record*, unsigned> RegNo;
+  for (unsigned i = 0, e = Regs.size(); i != e; ++i)
+    RegNo[Regs[i].TheDef] = i;
+  
+  for (unsigned i = 0, e = Regs.size(); i != e; ++i) {
+    Record* R = Regs[i].TheDef;
+    for (std::set<Record*>::iterator I = RegisterSubRegs[R].begin(),
+         E = RegisterSubRegs[R].end(); I != E; ++I) {
+      Record* RJ = *I;
+      // We have to increase the indices of both registers by one when
+      // computing the hash because, in the generated code, there
+      // will be an extra empty slot at register 0.
+      size_t index = ((i+1) + (RegNo[RJ]+1) * 37) % SubregHashTableSize;
+      unsigned ProbeAmt = 2;
+      while (SubregHashTable[index*2] != ~0U &&
+             SubregHashTable[index*2+1] != ~0U) {
+        index = (index + ProbeAmt) % SubregHashTableSize;
+        ProbeAmt += 2;
+      }
+      
+      SubregHashTable[index*2] = i;
+      SubregHashTable[index*2+1] = RegNo[RJ];
+    }
+  }
+  
+  if (SubregHashTableSize) {
+    std::string Namespace = Regs[0].TheDef->getValueAsString("Namespace");
+    
+    OS << "\n\n  unsigned SubregHashTable[] = {";
+    for (unsigned i = 0; i < SubregHashTableSize - 1; ++i) {
+      if (SubregHashTable[2*i] != ~0U) {
+        OS << getQualifiedName(Regs[SubregHashTable[2*i]].TheDef) << ", "
+           << getQualifiedName(Regs[SubregHashTable[2*i+1]].TheDef) << ", ";
+      } else {
+        OS << Namespace << "::NoRegister, " << Namespace << "::NoRegister, ";
+      }
+    }
+    
+    unsigned Idx = SubregHashTableSize*2-2;
+    if (SubregHashTable[Idx] != ~0U) {
+      OS << getQualifiedName(Regs[SubregHashTable[Idx]].TheDef) << ", "
+         << getQualifiedName(Regs[SubregHashTable[Idx+1]].TheDef) << "};\n";
+    } else {
+      OS << Namespace << "::NoRegister, " << Namespace << "::NoRegister};\n";
+    }
+    
+    OS << "  unsigned SubregHashTableSize = "
+       << SubregHashTableSize << ";\n";
+  } else {
+    OS << "\n\n  unsigned SubregHashTable[] = { ~0U, ~0U };\n"
+       << "  unsigned SubregHashTableSize = 1;\n";
+  }
+  
+  free(SubregHashTable);
 
   if (!RegisterAliases.empty())
     OS << "\n\n  // Register Alias Sets...\n";
@@ -607,7 +671,10 @@ void RegisterInfoEmitter::run(std::ostream &OS) {
      << "(int CallFrameSetupOpcode, int CallFrameDestroyOpcode)\n"
      << "  : TargetRegisterInfo(RegisterDescriptors, " << Registers.size()+1
      << ", RegisterClasses, RegisterClasses+" << RegisterClasses.size() <<",\n "
-     << "                 CallFrameSetupOpcode, CallFrameDestroyOpcode) {}\n\n";
+     << "                 CallFrameSetupOpcode, CallFrameDestroyOpcode) {\n"
+     << "  this->SubregHash = SubregHashTable;\n"
+     << "  this->SubregHashSize = SubregHashTableSize;\n"
+     << "}\n\n";
 
   // Collect all information about dwarf register numbers