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

2 files changed, 10 insertions, 4 deletions

diff --git a/utils/TableGen/CodeGenRegisters.cpp b/utils/TableGen/CodeGenRegisters.cpp
index daa7eab..6134225 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 2a337f0..942163e 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