diff options
author | Jakob Stoklund Olesen <stoklund@2pi.dk> | 2012-05-29 23:40:00 +0000 |
---|---|---|
committer | Jakob Stoklund Olesen <stoklund@2pi.dk> | 2012-05-29 23:40:00 +0000 |
commit | f52baf72c116d9cf8680d25a8e751ce354c7d44b (patch) | |
tree | 27377be4daa61fc002a16a1a3600ed9ce06a4bac /utils | |
parent | 988a089164fe88a9e1c95a5a94f93f377d017f77 (diff) | |
download | external_llvm-f52baf72c116d9cf8680d25a8e751ce354c7d44b.zip external_llvm-f52baf72c116d9cf8680d25a8e751ce354c7d44b.tar.gz external_llvm-f52baf72c116d9cf8680d25a8e751ce354c7d44b.tar.bz2 |
Emit register unit lists for each register.
Register units are already used internally in TableGen to compute
register pressure sets and overlapping registers. This patch makes them
available to the code generators.
The register unit lists are differentially encoded so they can be reused
for many related registers. This keeps the total size of the lists below
200 bytes for most targets. ARM has the largest table at 560 bytes.
Add an MCRegUnitIterator for traversing the register unit lists. It
provides an abstract interface so the representation can be changed in
the future without changing all clients.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@157650 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'utils')
-rw-r--r-- | utils/TableGen/CodeGenRegisters.cpp | 5 | ||||
-rw-r--r-- | utils/TableGen/CodeGenRegisters.h | 14 | ||||
-rw-r--r-- | utils/TableGen/RegisterInfoEmitter.cpp | 78 |
3 files changed, 93 insertions, 4 deletions
diff --git a/utils/TableGen/CodeGenRegisters.cpp b/utils/TableGen/CodeGenRegisters.cpp index 2b064aa..887f01b 100644 --- a/utils/TableGen/CodeGenRegisters.cpp +++ b/utils/TableGen/CodeGenRegisters.cpp @@ -83,6 +83,7 @@ CodeGenRegister::CodeGenRegister(Record *R, unsigned Enum) EnumValue(Enum), CostPerUse(R->getValueAsInt("CostPerUse")), CoveredBySubRegs(R->getValueAsBit("CoveredBySubRegs")), + NumNativeRegUnits(0), SubRegsComplete(false), SuperRegsComplete(false), TopoSig(~0u) @@ -397,6 +398,10 @@ CodeGenRegister::computeSubRegs(CodeGenRegBank &RegBank) { if (RegUnits.empty()) RegUnits.push_back(RegBank.newRegUnit(this)); + // We have now computed the native register units. More may be adopted later + // for balancing purposes. + NumNativeRegUnits = RegUnits.size(); + return SubRegs; } diff --git a/utils/TableGen/CodeGenRegisters.h b/utils/TableGen/CodeGenRegisters.h index 3046152..0c348c3 100644 --- a/utils/TableGen/CodeGenRegisters.h +++ b/utils/TableGen/CodeGenRegisters.h @@ -162,10 +162,18 @@ namespace llvm { // List of register units in ascending order. typedef SmallVector<unsigned, 16> RegUnitList; + // How many entries in RegUnitList are native? + unsigned NumNativeRegUnits; + // Get the list of register units. - // This is only valid after getSubRegs() completes. + // This is only valid after computeSubRegs() completes. const RegUnitList &getRegUnits() const { return RegUnits; } + // Get the native register units. This is a prefix of getRegUnits(). + ArrayRef<unsigned> getNativeRegUnits() const { + return makeArrayRef(RegUnits).slice(0, NumNativeRegUnits); + } + // Inherit register units from subregisters. // Return true if the RegUnits changed. bool inheritRegUnits(CodeGenRegBank &RegBank); @@ -554,6 +562,10 @@ namespace llvm { return RUID < NumNativeRegUnits; } + unsigned getNumNativeRegUnits() const { + return NumNativeRegUnits; + }; + RegUnit &getRegUnit(unsigned RUID) { return RegUnits[RUID]; } const RegUnit &getRegUnit(unsigned RUID) const { return RegUnits[RUID]; } diff --git a/utils/TableGen/RegisterInfoEmitter.cpp b/utils/TableGen/RegisterInfoEmitter.cpp index 3d50a82..0d0c325 100644 --- a/utils/TableGen/RegisterInfoEmitter.cpp +++ b/utils/TableGen/RegisterInfoEmitter.cpp @@ -454,6 +454,35 @@ static void printSubRegIndex(raw_ostream &OS, const CodeGenSubRegIndex *Idx) { OS << Idx->getQualifiedName(); } +// Differentially encoded register and regunit lists allow for better +// compression on regular register banks. The sequence is computed from the +// differential list as: +// +// out[0] = InitVal; +// out[n+1] = out[n] + diff[n]; // n = 0, 1, ... +// +// The initial value depends on the specific list. The list is terminated by a +// 0 differential which means we can't encode repeated elements. + +typedef SmallVector<uint16_t, 4> DiffVec; + +// Differentially encode a sequence of numbers into V. The starting value and +// terminating 0 are not added to V, so it will have the same size as List. +DiffVec &diffEncode(DiffVec &V, unsigned InitVal, ArrayRef<unsigned> List) { + assert(V.empty() && "Clear DiffVec before diffEncode."); + uint16_t Val = uint16_t(InitVal); + for (unsigned i = 0; i != List.size(); ++i) { + uint16_t Cur = List[i]; + V.push_back(Cur - Val); + Val = Cur; + } + return V; +} + +static void printDiff16(raw_ostream &OS, uint16_t Val) { + OS << SignExtend32<16>(Val); +} + // // runMCDesc - Print out MC register descriptions. // @@ -474,6 +503,11 @@ RegisterInfoEmitter::runMCDesc(raw_ostream &OS, CodeGenTarget &Target, SmallVector<RegVec, 4> OverlapLists(Regs.size()); SequenceToOffsetTable<RegVec, CodeGenRegister::Less> RegSeqs; + // Differentially encoded lists. + SequenceToOffsetTable<DiffVec> DiffSeqs; + SmallVector<DiffVec, 4> RegUnitLists(Regs.size()); + SmallVector<unsigned, 4> RegUnitInitScale(Regs.size()); + SequenceToOffsetTable<std::string> RegStrings; // Precompute register lists for the SequenceToOffsetTable. @@ -516,10 +550,36 @@ RegisterInfoEmitter::runMCDesc(raw_ostream &OS, CodeGenTarget &Target, // Finally, Suffix itself. OverlapList.insert(OverlapList.end(), Suffix.begin(), Suffix.end()); RegSeqs.add(OverlapList); + + // Differentially encode the register unit list, seeded by register number. + // First compute a scale factor that allows more diff-lists to be reused: + // + // D0 -> (S0, S1) + // D1 -> (S2, S3) + // + // A scale factor of 2 allows D0 and D1 to share a diff-list. The initial + // value for the differential decoder is the register number multiplied by + // the scale. + // + // Check the neighboring registers for arithmetic progressions. + unsigned ScaleA = ~0u, ScaleB = ~0u; + ArrayRef<unsigned> RUs = Reg->getNativeRegUnits(); + if (i > 0 && Regs[i-1]->getNativeRegUnits().size() == RUs.size()) + ScaleB = RUs.front() - Regs[i-1]->getNativeRegUnits().front(); + if (i+1 != Regs.size() && + Regs[i+1]->getNativeRegUnits().size() == RUs.size()) + ScaleA = Regs[i+1]->getNativeRegUnits().front() - RUs.front(); + unsigned Scale = std::min(ScaleB, ScaleA); + // Default the scale to 0 if it can't be encoded in 4 bits. + if (Scale >= 16) + Scale = 0; + RegUnitInitScale[i] = Scale; + DiffSeqs.add(diffEncode(RegUnitLists[i], Scale * Reg->EnumValue, RUs)); } // Compute the final layout of the sequence table. RegSeqs.layout(); + DiffSeqs.layout(); OS << "namespace llvm {\n\n"; @@ -530,6 +590,11 @@ RegisterInfoEmitter::runMCDesc(raw_ostream &OS, CodeGenTarget &Target, RegSeqs.emit(OS, printRegister); OS << "};\n\n"; + // Emit the shared table of differential lists. + OS << "extern const uint16_t " << TargetName << "RegDiffLists[] = {\n"; + DiffSeqs.emit(OS, printDiff16); + OS << "};\n\n"; + // Emit the string table. RegStrings.layout(); OS << "extern const char " << TargetName << "RegStrings[] = {\n"; @@ -538,7 +603,7 @@ RegisterInfoEmitter::runMCDesc(raw_ostream &OS, CodeGenTarget &Target, OS << "extern const MCRegisterDesc " << TargetName << "RegDesc[] = { // Descriptors\n"; - OS << " { " << RegStrings.get("") << ", 0, 0, 0 },\n"; + OS << " { " << RegStrings.get("") << ", 0, 0, 0, 0 },\n"; // Emit the register descriptors now. for (unsigned i = 0, e = Regs.size(); i != e; ++i) { @@ -546,7 +611,8 @@ RegisterInfoEmitter::runMCDesc(raw_ostream &OS, CodeGenTarget &Target, OS << " { " << RegStrings.get(Reg->getName()) << ", " << RegSeqs.get(OverlapLists[i]) << ", " << RegSeqs.get(SubRegLists[i]) << ", " - << RegSeqs.get(Reg->getSuperRegs()) << " },\n"; + << RegSeqs.get(Reg->getSuperRegs()) << ", " + << (DiffSeqs.get(RegUnitLists[i])*16 + RegUnitInitScale[i]) << " },\n"; } OS << "};\n\n"; // End of register descriptors... @@ -668,7 +734,10 @@ RegisterInfoEmitter::runMCDesc(raw_ostream &OS, CodeGenTarget &Target, << "unsigned DwarfFlavour = 0, unsigned EHFlavour = 0) {\n"; OS << " RI->InitMCRegisterInfo(" << TargetName << "RegDesc, " << Regs.size()+1 << ", RA, " << TargetName << "MCRegisterClasses, " - << RegisterClasses.size() << ", " << TargetName << "RegLists, " + << RegisterClasses.size() << ", " + << RegBank.getNumNativeRegUnits() << ", " + << TargetName << "RegLists, " + << TargetName << "RegDiffLists, " << TargetName << "RegStrings, "; if (SubRegIndices.size() != 0) OS << "(uint16_t*)" << TargetName << "SubRegTable, " @@ -1027,6 +1096,7 @@ RegisterInfoEmitter::runTargetDesc(raw_ostream &OS, CodeGenTarget &Target, // Emit the constructor of the class... OS << "extern const MCRegisterDesc " << TargetName << "RegDesc[];\n"; OS << "extern const uint16_t " << TargetName << "RegLists[];\n"; + OS << "extern const uint16_t " << TargetName << "RegDiffLists[];\n"; OS << "extern const char " << TargetName << "RegStrings[];\n"; if (SubRegIndices.size() != 0) OS << "extern const uint16_t *get" << TargetName @@ -1043,7 +1113,9 @@ RegisterInfoEmitter::runTargetDesc(raw_ostream &OS, CodeGenTarget &Target, << " InitMCRegisterInfo(" << TargetName << "RegDesc, " << Regs.size()+1 << ", RA,\n " << TargetName << "MCRegisterClasses, " << RegisterClasses.size() << ",\n" + << " " << RegBank.getNumNativeRegUnits() << ",\n" << " " << TargetName << "RegLists,\n" + << " " << TargetName << "RegDiffLists,\n" << " " << TargetName << "RegStrings,\n" << " "; if (SubRegIndices.size() != 0) |