Convert TargetRegisterInfo's super-register checking to use a pre-computed hash table...

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

diff --git a/include/llvm/Target/TargetRegisterInfo.h b/include/llvm/Target/TargetRegisterInfo.h
index bc1b731f99e6ec05b62c73252e8576b0f6ef4090..c9b94cafd8edcb27944b2d8630cb1799b55b954a 100644 (file)
--- a/include/llvm/Target/TargetRegisterInfo.h
+++ b/include/llvm/Target/TargetRegisterInfo.h
@@ -224,6 +224,8 @@ class TargetRegisterInfo {
 protected:
   const unsigned* SubregHash;
   const unsigned SubregHashSize;
+  const unsigned* SuperregHash;
+  const unsigned SuperregHashSize;
 public:
   typedef const TargetRegisterClass * const * regclass_iterator;
 private:
@@ -240,7 +242,9 @@ protected:
                      int CallFrameSetupOpcode = -1,
                      int CallFrameDestroyOpcode = -1,
                      const unsigned* subregs = 0,
-                     const unsigned subregsize = 0);
+                     const unsigned subregsize = 0,
+                    const unsigned* superregs = 0,
+                    const unsigned superregsize = 0);
   virtual ~TargetRegisterInfo();
 public:
 
@@ -379,8 +383,18 @@ public:
   /// isSuperRegister - Returns true if regB is a super-register of regA.
   ///
   bool isSuperRegister(unsigned regA, unsigned regB) const {
-    for (const unsigned *SR = getSuperRegisters(regA); *SR; ++SR)
-      if (*SR == regB) return true;
+    // SuperregHash is a simple quadratically probed hash table.
+    size_t index = (regA + regB * 37) & (SuperregHashSize-1);
+    unsigned ProbeAmt = 2;
+    while (SuperregHash[index*2] != 0 &&
+           SuperregHash[index*2+1] != 0) {
+      if (SuperregHash[index*2] == regA && SuperregHash[index*2+1] == regB)
+        return true;
+      
+      index = (index + ProbeAmt) & (SuperregHashSize-1);
+      ProbeAmt += 2;
+    }
+    
     return false;
   }
 

diff --git a/lib/Target/TargetRegisterInfo.cpp b/lib/Target/TargetRegisterInfo.cpp
index d9911e9e9a1840213e5afd99e45334071c2df13f..85ecd3d28a1e84b9291017eef076b96f354ee1a5 100644 (file)
--- a/lib/Target/TargetRegisterInfo.cpp
+++ b/lib/Target/TargetRegisterInfo.cpp
@@ -23,9 +23,11 @@ using namespace llvm;
 TargetRegisterInfo::TargetRegisterInfo(const TargetRegisterDesc *D, unsigned NR,
                              regclass_iterator RCB, regclass_iterator RCE,
                              int CFSO, int CFDO,
-                             const unsigned* subregs, const unsigned subregsize)
-  : SubregHash(subregs), SubregHashSize(subregsize), Desc(D), NumRegs(NR),
-    RegClassBegin(RCB), RegClassEnd(RCE) {
+                            const unsigned* subregs, const unsigned subregsize,
+                        const unsigned* superregs, const unsigned superregsize)
+  : SubregHash(subregs), SubregHashSize(subregsize),
+    SuperregHash(superregs), SuperregHashSize(superregsize),
+    Desc(D), NumRegs(NR), RegClassBegin(RCB), RegClassEnd(RCE) {
   assert(NumRegs < FirstVirtualRegister &&
          "Target has too many physical registers!");
 

diff --git a/utils/TableGen/RegisterInfoEmitter.cpp b/utils/TableGen/RegisterInfoEmitter.cpp
index 56c002054bc6b3039d80c44390ac6340ab4b8f66..f5f03e93f964291ea3afb3a0736dc89591cfe8c1 100644 (file)
--- a/utils/TableGen/RegisterInfoEmitter.cpp
+++ b/utils/TableGen/RegisterInfoEmitter.cpp
@@ -463,6 +463,83 @@ void RegisterInfoEmitter::run(std::ostream &OS) {
   
   delete [] SubregHashTable;
 
+
+  // Print the SuperregHashTable, a simple quadratically probed
+  // hash table for determining if a register is a super-register
+  // of another register.
+  unsigned NumSupRegs = 0;
+  RegNo.clear();
+  for (unsigned i = 0, e = Regs.size(); i != e; ++i) {
+    RegNo[Regs[i].TheDef] = i;
+    NumSupRegs += RegisterSuperRegs[Regs[i].TheDef].size();
+  }
+  
+  unsigned SuperregHashTableSize = 2 * NextPowerOf2(2 * NumSupRegs);
+  unsigned* SuperregHashTable = new unsigned[2 * SuperregHashTableSize];
+  std::fill(SuperregHashTable, SuperregHashTable + 2 * SuperregHashTableSize, ~0U);
+  
+  hashMisses = 0;
+  
+  for (unsigned i = 0, e = Regs.size(); i != e; ++i) {
+    Record* R = Regs[i].TheDef;
+    for (std::set<Record*>::iterator I = RegisterSuperRegs[R].begin(),
+         E = RegisterSuperRegs[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) & (SuperregHashTableSize-1);
+      unsigned ProbeAmt = 2;
+      while (SuperregHashTable[index*2] != ~0U &&
+             SuperregHashTable[index*2+1] != ~0U) {
+        index = (index + ProbeAmt) & (SuperregHashTableSize-1);
+        ProbeAmt += 2;
+        
+        hashMisses++;
+      }
+      
+      SuperregHashTable[index*2] = i;
+      SuperregHashTable[index*2+1] = RegNo[RJ];
+    }
+  }
+  
+  OS << "\n\n  // Number of hash collisions: " << hashMisses << "\n";
+  
+  if (SuperregHashTableSize) {
+    std::string Namespace = Regs[0].TheDef->getValueAsString("Namespace");
+    
+    OS << "  const unsigned SuperregHashTable[] = { ";
+    for (unsigned i = 0; i < SuperregHashTableSize - 1; ++i) {
+      if (i != 0)
+        // Insert spaces for nice formatting.
+        OS << "                                       ";
+      
+      if (SuperregHashTable[2*i] != ~0U) {
+        OS << getQualifiedName(Regs[SuperregHashTable[2*i]].TheDef) << ", "
+           << getQualifiedName(Regs[SuperregHashTable[2*i+1]].TheDef) << ", \n";
+      } else {
+        OS << Namespace << "::NoRegister, " << Namespace << "::NoRegister, \n";
+      }
+    }
+    
+    unsigned Idx = SuperregHashTableSize*2-2;
+    if (SuperregHashTable[Idx] != ~0U) {
+      OS << "                                       "
+         << getQualifiedName(Regs[SuperregHashTable[Idx]].TheDef) << ", "
+         << getQualifiedName(Regs[SuperregHashTable[Idx+1]].TheDef) << " };\n";
+    } else {
+      OS << Namespace << "::NoRegister, " << Namespace << "::NoRegister };\n";
+    }
+    
+    OS << "  const unsigned SuperregHashTableSize = "
+       << SuperregHashTableSize << ";\n";
+  } else {
+    OS << "  const unsigned SuperregHashTable[] = { ~0U, ~0U };\n"
+       << "  const unsigned SuperregHashTableSize = 1;\n";
+  }
+  
+  delete [] SuperregHashTable;
+
   if (!RegisterAliases.empty())
     OS << "\n\n  // Register Alias Sets...\n";
 
@@ -599,7 +676,8 @@ void RegisterInfoEmitter::run(std::ostream &OS) {
      << "  : TargetRegisterInfo(RegisterDescriptors, " << Registers.size()+1
      << ", RegisterClasses, RegisterClasses+" << RegisterClasses.size() <<",\n "
      << "                 CallFrameSetupOpcode, CallFrameDestroyOpcode,\n"
-     << "                 SubregHashTable, SubregHashTableSize) {\n"
+     << "                 SubregHashTable, SubregHashTableSize,\n"
+     << "                 SuperregHashTable, SuperregHashTableSize) {\n"
      << "}\n\n";
 
   // Collect all information about dwarf register numbers