Implement suggestions from Chris:

  - Use a more accurate heuristic for the size of the hashtable.
  - Use bitwise and instead of modulo since the size is a power of two.
  - Use new[] instead of malloc().

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

diff --git a/include/llvm/Target/TargetRegisterInfo.h b/include/llvm/Target/TargetRegisterInfo.h
index b385559178337bf12d79a72efb5498ea5ee8f87f..7e1320f87a4451a0116ec124d5cd44949438c135 100644 (file)
--- a/include/llvm/Target/TargetRegisterInfo.h
+++ b/include/llvm/Target/TargetRegisterInfo.h
@@ -413,14 +413,14 @@ public:
   ///
   bool isSubRegister(unsigned regA, unsigned regB) const {
     // SubregHash is a simple quadratically probed hash table.
-    size_t index = (regA + regB * 37) % SubregHashSize;
+    size_t index = (regA + regB * 37) & (SubregHashSize-1);
     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;
+      index = (index + ProbeAmt) & (SubregHashSize-1);
       ProbeAmt += 2;
     }
     

diff --git a/utils/TableGen/RegisterInfoEmitter.cpp b/utils/TableGen/RegisterInfoEmitter.cpp
index 64e1dfee0f58846b5b68ea91c45dff46b926a2ad..ec1b99d023a527089e87595910115f6d809eae83 100644 (file)
--- a/utils/TableGen/RegisterInfoEmitter.cpp
+++ b/utils/TableGen/RegisterInfoEmitter.cpp
@@ -466,15 +466,16 @@ void RegisterInfoEmitter::run(std::ostream &OS) {
   // 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;
-  
+  unsigned NumSubRegs = 0;
   std::map<Record*, unsigned> RegNo;
-  for (unsigned i = 0, e = Regs.size(); i != e; ++i)
+  for (unsigned i = 0, e = Regs.size(); i != e; ++i) {
     RegNo[Regs[i].TheDef] = i;
+    NumSubRegs += RegisterSubRegs[Regs[i].TheDef].size();
+  }
+  
+  unsigned SubregHashTableSize = NextPowerOf2(2 * NumSubRegs);
+  unsigned* SubregHashTable = new unsigned[2 * SubregHashTableSize];
+  std::fill(SubregHashTable, SubregHashTable + 2 * SubregHashTableSize, ~0U);
   
   for (unsigned i = 0, e = Regs.size(); i != e; ++i) {
     Record* R = Regs[i].TheDef;
@@ -484,11 +485,11 @@ void RegisterInfoEmitter::run(std::ostream &OS) {
       // 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;
+      size_t index = ((i+1) + (RegNo[RJ]+1) * 37) & (SubregHashTableSize-1);
       unsigned ProbeAmt = 2;
       while (SubregHashTable[index*2] != ~0U &&
              SubregHashTable[index*2+1] != ~0U) {
-        index = (index + ProbeAmt) % SubregHashTableSize;
+        index = (index + ProbeAmt) & (SubregHashTableSize-1);
         ProbeAmt += 2;
       }