From b7110cf5b5e4832e8ded6db7ab7577e3cfa2c462 Mon Sep 17 00:00:00 2001 From: Chad Rosier Date: Thu, 27 Jun 2013 19:38:13 +0000 Subject: [PATCH] Improve the compression of the tablegen DiffLists by introducing a new sort algorithm when assigning EnumValues to the synthesized registers. The current algorithm, LessRecord, uses the StringRef compare_numeric function. This function compares strings, while handling embedded numbers. For example, the R600 backend registers are sorted as follows: T1 T1_W T1_X T1_XYZW T1_Y T1_Z T2 T2_W T2_X T2_XYZW T2_Y T2_Z In this example, the 'scaling factor' is dEnum/dN = 6 because T0, T1, T2 have an EnumValue offset of 6 from one another. However, in other parts of the register bank, the scaling factors are different: dEnum/dN = 5: KC0_128_W KC0_128_X KC0_128_XYZW KC0_128_Y KC0_128_Z KC0_129_W KC0_129_X KC0_129_XYZW KC0_129_Y KC0_129_Z The diff lists do not work correctly because different kinds of registers have different 'scaling factors'. This new algorithm, LessRecordRegister, tries to enforce a scaling factor of 1. For example, the registers are now sorted as follows: T1 T2 T3 ... T0_W T1_W T2_W ... T0_X T1_X T2_X ... KC0_128_W KC0_129_W KC0_130_W ... For the Mips and R600 I see a 19% and 6% reduction in size, respectively. I did see a few small regressions, but the differences were on the order of a few bytes (e.g., AArch64 was 16 bytes). I suspect there will be even greater wins for targets with larger register files. Patch reviewed by Jakob. rdar://14006013 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@185094 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/TableGen/Record.h | 80 ++++++++++++++++++++++++++ test/MC/ARM/basic-arm-instructions.s | 36 ++++++------ utils/TableGen/CodeGenRegisters.cpp | 12 +++- utils/TableGen/RegisterInfoEmitter.cpp | 2 +- 4 files changed, 108 insertions(+), 22 deletions(-) diff --git a/include/llvm/TableGen/Record.h b/include/llvm/TableGen/Record.h index 76ee69dd8db..63b72c8a738 100644 --- a/include/llvm/TableGen/Record.h +++ b/include/llvm/TableGen/Record.h @@ -1731,6 +1731,86 @@ struct LessRecordFieldName { } }; +struct LessRecordRegister { + static size_t min(size_t a, size_t b) { return a < b ? a : b; } + static bool ascii_isdigit(char x) { return x >= '0' && x <= '9'; } + + struct RecordParts { + SmallVector, 4> Parts; + + RecordParts(StringRef Rec) { + if (Rec.empty()) + return; + + size_t Len = 0; + const char *Start = Rec.data(); + const char *Curr = Start; + bool isDigitPart = ascii_isdigit(Curr[0]); + for (size_t I = 0, E = Rec.size(); I != E; ++I, ++Len) { + bool isDigit = ascii_isdigit(Curr[I]); + if (isDigit != isDigitPart) { + Parts.push_back(std::make_pair(isDigitPart, StringRef(Start, Len))); + Len = 0; + Start = &Curr[I]; + isDigitPart = ascii_isdigit(Curr[I]); + } + } + // Push the last part. + Parts.push_back(std::make_pair(isDigitPart, StringRef(Start, Len))); + } + + size_t size() { return Parts.size(); } + + std::pair getPart(size_t i) { + assert (i < Parts.size() && "Invalid idx!"); + return Parts[i]; + } + }; + + bool operator()(const Record *Rec1, const Record *Rec2) const { + RecordParts LHSParts(StringRef(Rec1->getName())); + RecordParts RHSParts(StringRef(Rec2->getName())); + + size_t LHSNumParts = LHSParts.size(); + size_t RHSNumParts = RHSParts.size(); + assert (LHSNumParts && RHSNumParts && "Expected at least one part!"); + + if (LHSNumParts != RHSNumParts) + return LHSNumParts < RHSNumParts; + + // We expect the registers to be of the form [_a-zA-z]+([0-9]*[_a-zA-Z]*)*. + for (size_t I = 0, E = LHSNumParts; I < E; I+=2) { + std::pair LHSPart = LHSParts.getPart(I); + std::pair RHSPart = RHSParts.getPart(I); + if ((I & 1) == 0) { // Expect even part to always be alpha. + assert (LHSPart.first == false && RHSPart.first == false && + "Expected both parts to be alpha."); + if (int Res = LHSPart.second.compare(RHSPart.second)) + return Res < 0; + } + } + for (size_t I = 1, E = LHSNumParts; I < E; I+=2) { + std::pair LHSPart = LHSParts.getPart(I); + std::pair RHSPart = RHSParts.getPart(I); + if (I & 1) { // Expect odd part to always be numeric. + assert (LHSPart.first == true && RHSPart.first == true && + "Expected both parts to be numeric."); + if (LHSPart.second.size() != RHSPart.second.size()) + return LHSPart.second.size() < RHSPart.second.size(); + + unsigned LHSVal, RHSVal; + if (LHSPart.second.getAsInteger(10, LHSVal)) + assert("Unable to convert LHS to integer."); + if (RHSPart.second.getAsInteger(10, RHSVal)) + assert("Unable to convert RHS to integer."); + if (LHSVal != RHSVal) + return LHSVal < RHSVal; + } + } + return LHSNumParts < RHSNumParts; + } +}; + raw_ostream &operator<<(raw_ostream &OS, const RecordKeeper &RK); /// QualifyName - Return an Init with a qualifier prefix referring diff --git a/test/MC/ARM/basic-arm-instructions.s b/test/MC/ARM/basic-arm-instructions.s index a7c54ff3a56..aaff80ca35d 100644 --- a/test/MC/ARM/basic-arm-instructions.s +++ b/test/MC/ARM/basic-arm-instructions.s @@ -897,17 +897,17 @@ Lforward: ldm r0, {r0, r2, lr}^ ldm sp!, {r0-r3, pc}^ -@ CHECK: ldm r2, {r1, r3, r4, r5, r6, sp} @ encoding: [0x7a,0x20,0x92,0xe8] -@ CHECK: ldm r2, {r1, r3, r4, r5, r6, sp} @ encoding: [0x7a,0x20,0x92,0xe8] -@ CHECK: ldmib r2, {r1, r3, r4, r5, r6, sp} @ encoding: [0x7a,0x20,0x92,0xe9] -@ CHECK: ldmda r2, {r1, r3, r4, r5, r6, sp} @ encoding: [0x7a,0x20,0x12,0xe8] -@ CHECK: ldmdb r2, {r1, r3, r4, r5, r6, sp} @ encoding: [0x7a,0x20,0x12,0xe9] -@ CHECK: ldm r2, {r1, r3, r4, r5, r6, sp} @ encoding: [0x7a,0x20,0x92,0xe8] - -@ CHECK: ldm r2!, {r1, r3, r4, r5, r6, sp} @ encoding: [0x7a,0x20,0xb2,0xe8] -@ CHECK: ldmib r2!, {r1, r3, r4, r5, r6, sp} @ encoding: [0x7a,0x20,0xb2,0xe9] -@ CHECK: ldmda r2!, {r1, r3, r4, r5, r6, sp} @ encoding: [0x7a,0x20,0x32,0xe8] -@ CHECK: ldmdb r2!, {r1, r3, r4, r5, r6, sp} @ encoding: [0x7a,0x20,0x32,0xe9] +@ CHECK: ldm r2, {sp, r1, r3, r4, r5, r6} @ encoding: [0x7a,0x20,0x92,0xe8] +@ CHECK: ldm r2, {sp, r1, r3, r4, r5, r6} @ encoding: [0x7a,0x20,0x92,0xe8] +@ CHECK: ldmib r2, {sp, r1, r3, r4, r5, r6} @ encoding: [0x7a,0x20,0x92,0xe9] +@ CHECK: ldmda r2, {sp, r1, r3, r4, r5, r6} @ encoding: [0x7a,0x20,0x12,0xe8] +@ CHECK: ldmdb r2, {sp, r1, r3, r4, r5, r6} @ encoding: [0x7a,0x20,0x12,0xe9] +@ CHECK: ldm r2, {sp, r1, r3, r4, r5, r6} @ encoding: [0x7a,0x20,0x92,0xe8] + +@ CHECK: ldm r2!, {sp, r1, r3, r4, r5, r6} @ encoding: [0x7a,0x20,0xb2,0xe8] +@ CHECK: ldmib r2!, {sp, r1, r3, r4, r5, r6} @ encoding: [0x7a,0x20,0xb2,0xe9] +@ CHECK: ldmda r2!, {sp, r1, r3, r4, r5, r6} @ encoding: [0x7a,0x20,0x32,0xe8] +@ CHECK: ldmdb r2!, {sp, r1, r3, r4, r5, r6} @ encoding: [0x7a,0x20,0x32,0xe9] @ CHECK: ldm r0, {lr, r0, r2} ^ @ encoding: [0x05,0x40,0xd0,0xe8] @ CHECK: ldm sp!, {pc, r0, r1, r2, r3} ^ @ encoding: [0x0f,0x80,0xfd,0xe8] @@ -2332,17 +2332,17 @@ Lforward: stmda sp!, {r1,r3-r6} stmdb r0!, {r1,r5,r7,sp} -@ CHECK: stm r2, {r1, r3, r4, r5, r6, sp} @ encoding: [0x7a,0x20,0x82,0xe8] +@ CHECK: stm r2, {sp, r1, r3, r4, r5, r6} @ encoding: [0x7a,0x20,0x82,0xe8] @ CHECK: stm r3, {lr, r1, r3, r4, r5, r6} @ encoding: [0x7a,0x40,0x83,0xe8] -@ CHECK: stmib r4, {r1, r3, r4, r5, r6, sp} @ encoding: [0x7a,0x20,0x84,0xe9] -@ CHECK: stmda r5, {r1, r3, r4, r5, r6, sp} @ encoding: [0x7a,0x20,0x05,0xe8] +@ CHECK: stmib r4, {sp, r1, r3, r4, r5, r6} @ encoding: [0x7a,0x20,0x84,0xe9] +@ CHECK: stmda r5, {sp, r1, r3, r4, r5, r6} @ encoding: [0x7a,0x20,0x05,0xe8] @ CHECK: stmdb r6, {r1, r3, r4, r5, r6, r8} @ encoding: [0x7a,0x01,0x06,0xe9] -@ CHECK: stmdb sp, {r1, r3, r4, r5, r6, sp} @ encoding: [0x7a,0x20,0x0d,0xe9] +@ CHECK: stmdb sp, {sp, r1, r3, r4, r5, r6} @ encoding: [0x7a,0x20,0x0d,0xe9] -@ CHECK: stm r8!, {r1, r3, r4, r5, r6, sp} @ encoding: [0x7a,0x20,0xa8,0xe8] -@ CHECK: stmib r9!, {r1, r3, r4, r5, r6, sp} @ encoding: [0x7a,0x20,0xa9,0xe9] +@ CHECK: stm r8!, {sp, r1, r3, r4, r5, r6} @ encoding: [0x7a,0x20,0xa8,0xe8] +@ CHECK: stmib r9!, {sp, r1, r3, r4, r5, r6} @ encoding: [0x7a,0x20,0xa9,0xe9] @ CHECK: stmda sp!, {r1, r3, r4, r5, r6} @ encoding: [0x7a,0x00,0x2d,0xe8] -@ CHECK: stmdb r0!, {r1, r5, r7, sp} @ encoding: [0xa2,0x20,0x20,0xe9] +@ CHECK: stmdb r0!, {sp, r1, r5, r7} @ encoding: [0xa2,0x20,0x20,0xe9] @------------------------------------------------------------------------------ diff --git a/utils/TableGen/CodeGenRegisters.cpp b/utils/TableGen/CodeGenRegisters.cpp index daa7eab658d..61342254923 100644 --- a/utils/TableGen/CodeGenRegisters.cpp +++ b/utils/TableGen/CodeGenRegisters.cpp @@ -938,7 +938,7 @@ CodeGenRegBank::CodeGenRegBank(RecordKeeper &Records) { // Read in the register definitions. std::vector Regs = Records.getAllDerivedDefinitions("Register"); - std::sort(Regs.begin(), Regs.end(), LessRecord()); + std::sort(Regs.begin(), Regs.end(), LessRecordRegister()); Registers.reserve(Regs.size()); // Assign the enumeration values. for (unsigned i = 0, e = Regs.size(); i != e; ++i) @@ -947,10 +947,16 @@ CodeGenRegBank::CodeGenRegBank(RecordKeeper &Records) { // Expand tuples and number the new registers. std::vector Tups = Records.getAllDerivedDefinitions("RegisterTuples"); + + std::vector TupRegsCopy; for (unsigned i = 0, e = Tups.size(); i != e; ++i) { const std::vector *TupRegs = Sets.expand(Tups[i]); - for (unsigned j = 0, je = TupRegs->size(); j != je; ++j) - getReg((*TupRegs)[j]); + TupRegsCopy.reserve(TupRegs->size()); + TupRegsCopy.assign(TupRegs->begin(), TupRegs->end()); + std::sort(TupRegsCopy.begin(), TupRegsCopy.end(), LessRecordRegister()); + for (unsigned j = 0, je = TupRegsCopy.size(); j != je; ++j) + getReg((TupRegsCopy)[j]); + TupRegsCopy.clear(); } // Now all the registers are known. Build the object graph of explicit diff --git a/utils/TableGen/RegisterInfoEmitter.cpp b/utils/TableGen/RegisterInfoEmitter.cpp index 2a337f0dbe0..942163e77dc 100644 --- a/utils/TableGen/RegisterInfoEmitter.cpp +++ b/utils/TableGen/RegisterInfoEmitter.cpp @@ -309,7 +309,7 @@ RegisterInfoEmitter::EmitRegMappingTables(raw_ostream &OS, const std::vector &Regs, bool isCtor) { // Collect all information about dwarf register numbers - typedef std::map, LessRecord> DwarfRegNumsMapTy; + typedef std::map, LessRecordRegister> DwarfRegNumsMapTy; DwarfRegNumsMapTy DwarfRegNums; // First, just pull all provided information to the map -- 2.34.1