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

4 files changed, 108 insertions, 22 deletions

diff --git a/include/llvm/TableGen/Record.h b/include/llvm/TableGen/Record.h
index 76ee69dd8d..63b72c8a73 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<std::pair< bool, StringRef>, 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<bool, StringRef> 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<bool, StringRef> LHSPart = LHSParts.getPart(I);
+      std::pair<bool, StringRef> 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<bool, StringRef> LHSPart = LHSParts.getPart(I);
+      std::pair<bool, StringRef> 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 a7c54ff3a5..aaff80ca35 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 daa7eab658..6134225492 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<Record*> 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<Record*> Tups =
     Records.getAllDerivedDefinitions("RegisterTuples");
+
+  std::vector<Record*> TupRegsCopy;
   for (unsigned i = 0, e = Tups.size(); i != e; ++i) {
     const std::vector<Record*> *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 2a337f0dbe..942163e77d 100644
--- a/utils/TableGen/RegisterInfoEmitter.cpp
+++ b/utils/TableGen/RegisterInfoEmitter.cpp
@@ -309,7 +309,7 @@ RegisterInfoEmitter::EmitRegMappingTables(raw_ostream &OS,
                                        const std::vector<CodeGenRegister*> &Regs,
                                           bool isCtor) {
   // Collect all information about dwarf register numbers
-  typedef std::map<Record*, std::vector<int64_t>, LessRecord> DwarfRegNumsMapTy;
+  typedef std::map<Record*, std::vector<int64_t>, LessRecordRegister> DwarfRegNumsMapTy;
   DwarfRegNumsMapTy DwarfRegNums;
 
   // First, just pull all provided information to the map