From 3ca15c989ca0e09085648771db368d8c94ee1f19 Mon Sep 17 00:00:00 2001 From: Owen Anderson Date: Thu, 9 Apr 2009 22:19:30 +0000 Subject: [PATCH] Give register alias checking the hash table treatment too. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@68730 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Target/TargetRegisterInfo.h | 19 +++++- lib/Target/TargetRegisterInfo.cpp | 4 +- utils/TableGen/RegisterInfoEmitter.cpp | 79 +++++++++++++++++++++++- 3 files changed, 97 insertions(+), 5 deletions(-) diff --git a/include/llvm/Target/TargetRegisterInfo.h b/include/llvm/Target/TargetRegisterInfo.h index c9b94cafd8e..45f9f2db901 100644 --- a/include/llvm/Target/TargetRegisterInfo.h +++ b/include/llvm/Target/TargetRegisterInfo.h @@ -226,6 +226,8 @@ protected: const unsigned SubregHashSize; const unsigned* SuperregHash; const unsigned SuperregHashSize; + const unsigned* AliasesHash; + const unsigned AliasesHashSize; public: typedef const TargetRegisterClass * const * regclass_iterator; private: @@ -244,7 +246,9 @@ protected: const unsigned* subregs = 0, const unsigned subregsize = 0, const unsigned* superregs = 0, - const unsigned superregsize = 0); + const unsigned superregsize = 0, + const unsigned* aliases = 0, + const unsigned aliasessize = 0); virtual ~TargetRegisterInfo(); public: @@ -346,8 +350,17 @@ public: /// areAliases - Returns true if the two registers alias each other, false /// otherwise bool areAliases(unsigned regA, unsigned regB) const { - for (const unsigned *Alias = getAliasSet(regA); *Alias; ++Alias) - if (*Alias == regB) return true; + size_t index = (regA + regB * 37) & (AliasesHashSize-1); + unsigned ProbeAmt = 0; + while (AliasesHash[index*2] != 0 && + AliasesHash[index*2+1] != 0) { + if (AliasesHash[index*2] == regA && AliasesHash[index*2+1] == regB) + return true; + + index = (index + ProbeAmt) & (AliasesHashSize-1); + ProbeAmt += 2; + } + return false; } diff --git a/lib/Target/TargetRegisterInfo.cpp b/lib/Target/TargetRegisterInfo.cpp index 85ecd3d28a1..eca074cc743 100644 --- a/lib/Target/TargetRegisterInfo.cpp +++ b/lib/Target/TargetRegisterInfo.cpp @@ -24,9 +24,11 @@ TargetRegisterInfo::TargetRegisterInfo(const TargetRegisterDesc *D, unsigned NR, regclass_iterator RCB, regclass_iterator RCE, int CFSO, int CFDO, const unsigned* subregs, const unsigned subregsize, - const unsigned* superregs, const unsigned superregsize) + const unsigned* superregs, const unsigned superregsize, + const unsigned* aliases, const unsigned aliasessize) : SubregHash(subregs), SubregHashSize(subregsize), SuperregHash(superregs), SuperregHashSize(superregsize), + AliasesHash(aliases), AliasesHashSize(aliasessize), 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 f5f03e93f96..d45f565e25c 100644 --- a/utils/TableGen/RegisterInfoEmitter.cpp +++ b/utils/TableGen/RegisterInfoEmitter.cpp @@ -540,6 +540,82 @@ void RegisterInfoEmitter::run(std::ostream &OS) { delete [] SuperregHashTable; + + // Print the AliasHashTable, a simple quadratically probed + // hash table for determining if a register aliases another register. + unsigned NumAliases = 0; + RegNo.clear(); + for (unsigned i = 0, e = Regs.size(); i != e; ++i) { + RegNo[Regs[i].TheDef] = i; + NumAliases += RegisterAliases[Regs[i].TheDef].size(); + } + + unsigned AliasesHashTableSize = 2 * NextPowerOf2(2 * NumAliases); + unsigned* AliasesHashTable = new unsigned[2 * AliasesHashTableSize]; + std::fill(AliasesHashTable, AliasesHashTable + 2 * AliasesHashTableSize, ~0U); + + hashMisses = 0; + + for (unsigned i = 0, e = Regs.size(); i != e; ++i) { + Record* R = Regs[i].TheDef; + for (std::set::iterator I = RegisterAliases[R].begin(), + E = RegisterAliases[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) & (AliasesHashTableSize-1); + unsigned ProbeAmt = 2; + while (AliasesHashTable[index*2] != ~0U && + AliasesHashTable[index*2+1] != ~0U) { + index = (index + ProbeAmt) & (AliasesHashTableSize-1); + ProbeAmt += 2; + + hashMisses++; + } + + AliasesHashTable[index*2] = i; + AliasesHashTable[index*2+1] = RegNo[RJ]; + } + } + + OS << "\n\n // Number of hash collisions: " << hashMisses << "\n"; + + if (AliasesHashTableSize) { + std::string Namespace = Regs[0].TheDef->getValueAsString("Namespace"); + + OS << " const unsigned AliasesHashTable[] = { "; + for (unsigned i = 0; i < AliasesHashTableSize - 1; ++i) { + if (i != 0) + // Insert spaces for nice formatting. + OS << " "; + + if (AliasesHashTable[2*i] != ~0U) { + OS << getQualifiedName(Regs[AliasesHashTable[2*i]].TheDef) << ", " + << getQualifiedName(Regs[AliasesHashTable[2*i+1]].TheDef) << ", \n"; + } else { + OS << Namespace << "::NoRegister, " << Namespace << "::NoRegister, \n"; + } + } + + unsigned Idx = AliasesHashTableSize*2-2; + if (AliasesHashTable[Idx] != ~0U) { + OS << " " + << getQualifiedName(Regs[AliasesHashTable[Idx]].TheDef) << ", " + << getQualifiedName(Regs[AliasesHashTable[Idx+1]].TheDef) << " };\n"; + } else { + OS << Namespace << "::NoRegister, " << Namespace << "::NoRegister };\n"; + } + + OS << " const unsigned AliasesHashTableSize = " + << AliasesHashTableSize << ";\n"; + } else { + OS << " const unsigned AliasesHashTable[] = { ~0U, ~0U };\n" + << " const unsigned AliasesHashTableSize = 1;\n"; + } + + delete [] AliasesHashTable; + if (!RegisterAliases.empty()) OS << "\n\n // Register Alias Sets...\n"; @@ -677,7 +753,8 @@ void RegisterInfoEmitter::run(std::ostream &OS) { << ", RegisterClasses, RegisterClasses+" << RegisterClasses.size() <<",\n " << " CallFrameSetupOpcode, CallFrameDestroyOpcode,\n" << " SubregHashTable, SubregHashTableSize,\n" - << " SuperregHashTable, SuperregHashTableSize) {\n" + << " SuperregHashTable, SuperregHashTableSize,\n" + << " AliasesHashTable, AliasesHashTableSize) {\n" << "}\n\n"; // Collect all information about dwarf register numbers -- 2.34.1