Reapply 153764 and 153761 with a fix.

Use an explicit comparator instead of the default.

The sets are sorted, but not using the default comparator. Hopefully,
this will unbreak the Linux builders.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@153772 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 80 insertions, 103 deletions

diff --git a/utils/TableGen/RegisterInfoEmitter.cpp b/utils/TableGen/RegisterInfoEmitter.cpp
index f082cfa991..338e6aebdb 100644
--- a/utils/TableGen/RegisterInfoEmitter.cpp
+++ b/utils/TableGen/RegisterInfoEmitter.cpp
@@ -16,6 +16,7 @@
 #include "RegisterInfoEmitter.h"
 #include "CodeGenTarget.h"
 #include "CodeGenRegisters.h"
+#include "SequenceToOffsetTable.h"
 #include "llvm/TableGen/Record.h"
 #include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/StringExtras.h"
@@ -259,6 +260,14 @@ public:
   }
 };
 
+static void printRegister(raw_ostream &OS, const CodeGenRegister *Reg) {
+  OS << getQualifiedName(Reg->TheDef);
+}
+
+static void printSimpleValueType(raw_ostream &OS, MVT::SimpleValueType VT) {
+  OS << getEnumName(VT);
+}
+
 //
 // runMCDesc - Print out MC register descriptions.
 //
@@ -270,98 +279,79 @@ RegisterInfoEmitter::runMCDesc(raw_ostream &OS, CodeGenTarget &Target,
   OS << "\n#ifdef GET_REGINFO_MC_DESC\n";
   OS << "#undef GET_REGINFO_MC_DESC\n";
 
+  const std::vector<CodeGenRegister*> &Regs = RegBank.getRegisters();
   std::map<const CodeGenRegister*, CodeGenRegister::Set> Overlaps;
   RegBank.computeOverlaps(Overlaps);
 
-  OS << "namespace llvm {\n\n";
-
-  const std::string &TargetName = Target.getName();
-
-  const std::vector<CodeGenRegister*> &Regs = RegBank.getRegisters();
-
-  OS << "extern const uint16_t " << TargetName << "RegOverlaps[] = {\n";
+  // The lists of sub-registers, super-registers, and overlaps all go in the
+  // same array. That allows us to share suffixes.
+  typedef std::vector<const CodeGenRegister*> RegVec;
+  SmallVector<RegVec, 4> SubRegLists(Regs.size());
+  SmallVector<RegVec, 4> OverlapLists(Regs.size());
+  SequenceToOffsetTable<RegVec, CodeGenRegister::Less> RegSeqs;
 
-  // Emit an overlap list for all registers.
+  // Precompute register lists for the SequenceToOffsetTable.
   for (unsigned i = 0, e = Regs.size(); i != e; ++i) {
     const CodeGenRegister *Reg = Regs[i];
-    const CodeGenRegister::Set &O = Overlaps[Reg];
-    // Move Reg to the front so TRI::getAliasSet can share the list.
-    OS << "  /* " << Reg->getName() << "_Overlaps */ "
-       << getQualifiedName(Reg->TheDef) << ", ";
-    for (CodeGenRegister::Set::const_iterator I = O.begin(), E = O.end();
-         I != E; ++I)
-      if (*I != Reg)
-        OS << getQualifiedName((*I)->TheDef) << ", ";
-    OS << "0,\n";
-  }
-  OS << "};\n\n";
 
-  OS << "extern const uint16_t " << TargetName << "SubRegsSet[] = {\n";
-  // Emit the empty sub-registers list
-  OS << "  /* Empty_SubRegsSet */ 0,\n";
-  // Loop over all of the registers which have sub-registers, emitting the
-  // sub-registers list to memory.
-  for (unsigned i = 0, e = Regs.size(); i != e; ++i) {
-    const CodeGenRegister &Reg = *Regs[i];
-    if (Reg.getSubRegs().empty())
-     continue;
-    // getSubRegs() orders by SubRegIndex. We want a topological order.
+    // Compute the ordered sub-register list.
     SetVector<const CodeGenRegister*> SR;
-    Reg.addSubRegsPreOrder(SR, RegBank);
-    OS << "  /* " << Reg.getName() << "_SubRegsSet */ ";
-    for (unsigned j = 0, je = SR.size(); j != je; ++j)
-      OS << getQualifiedName(SR[j]->TheDef) << ", ";
-    OS << "0,\n";
+    Reg->addSubRegsPreOrder(SR, RegBank);
+    RegVec &SubRegList = SubRegLists[i];
+    SubRegList.assign(SR.begin(), SR.end());
+    RegSeqs.add(SubRegList);
+
+    // Super-registers are already computed.
+    const RegVec &SuperRegList = Reg->getSuperRegs();
+    RegSeqs.add(SuperRegList);
+
+    // The list of overlaps doesn't need to have any particular order, except
+    // Reg itself must be the first element. Pick an ordering that has one of
+    // the other lists as a suffix.
+    RegVec &OverlapList = OverlapLists[i];
+    const RegVec &Suffix = SubRegList.size() > SuperRegList.size() ?
+                           SubRegList : SuperRegList;
+    CodeGenRegister::Set Omit(Suffix.begin(), Suffix.end());
+
+    // First element is Reg itself.
+    OverlapList.push_back(Reg);
+    Omit.insert(Reg);
+
+    // Any elements not in Suffix.
+    const CodeGenRegister::Set &OSet = Overlaps[Reg];
+    std::set_difference(OSet.begin(), OSet.end(),
+                        Omit.begin(), Omit.end(),
+                        std::back_inserter(OverlapList),
+                        CodeGenRegister::Less());
+
+    // Finally, Suffix itself.
+    OverlapList.insert(OverlapList.end(), Suffix.begin(), Suffix.end());
+    RegSeqs.add(OverlapList);
   }
-  OS << "};\n\n";
 
-  OS << "extern const uint16_t " << TargetName << "SuperRegsSet[] = {\n";
-  // Emit the empty super-registers list
-  OS << "  /* Empty_SuperRegsSet */ 0,\n";
-  // Loop over all of the registers which have super-registers, emitting the
-  // super-registers list to memory.
-  for (unsigned i = 0, e = Regs.size(); i != e; ++i) {
-    const CodeGenRegister &Reg = *Regs[i];
-    const CodeGenRegister::SuperRegList &SR = Reg.getSuperRegs();
-    if (SR.empty())
-      continue;
-    OS << "  /* " << Reg.getName() << "_SuperRegsSet */ ";
-    for (unsigned j = 0, je = SR.size(); j != je; ++j)
-      OS << getQualifiedName(SR[j]->TheDef) << ", ";
-    OS << "0,\n";
-  }
+  // Compute the final layout of the sequence table.
+  RegSeqs.layout();
+
+  OS << "namespace llvm {\n\n";
+
+  const std::string &TargetName = Target.getName();
+
+  // Emit the shared table of register lists.
+  OS << "extern const uint16_t " << TargetName << "RegLists[] = {\n";
+  RegSeqs.emit(OS, printRegister);
   OS << "};\n\n";
 
   OS << "extern const MCRegisterDesc " << TargetName
      << "RegDesc[] = { // Descriptors\n";
   OS << "  { \"NOREG\", 0, 0, 0 },\n";
 
-  // Now that register alias and sub-registers sets have been emitted, emit the
-  // register descriptors now.
-  unsigned OverlapsIndex = 0;
-  unsigned SubRegIndex = 1; // skip 1 for empty set
-  unsigned SuperRegIndex = 1; // skip 1 for empty set
+  // Emit the register descriptors now.
   for (unsigned i = 0, e = Regs.size(); i != e; ++i) {
     const CodeGenRegister *Reg = Regs[i];
-    OS << "  { \"";
-    OS << Reg->getName() << "\", /* " << Reg->getName() << "_Overlaps */ "
-       << OverlapsIndex << ", ";
-    OverlapsIndex += Overlaps[Reg].size() + 1;
-    if (!Reg->getSubRegs().empty()) {
-      OS << "/* " << Reg->getName() << "_SubRegsSet */ " << SubRegIndex
-         << ", ";
-      // FIXME not very nice to recalculate this
-      SetVector<const CodeGenRegister*> SR;
-      Reg->addSubRegsPreOrder(SR, RegBank);
-      SubRegIndex += SR.size() + 1;
-    } else
-      OS << "/* Empty_SubRegsSet */ 0, ";
-    if (!Reg->getSuperRegs().empty()) {
-      OS << "/* " << Reg->getName() << "_SuperRegsSet */ " << SuperRegIndex;
-      SuperRegIndex += Reg->getSuperRegs().size() + 1;
-    } else
-      OS << "/* Empty_SuperRegsSet */ 0";
-    OS << " },\n";
+    OS << "  { \"" << Reg->getName() << "\", "
+       << RegSeqs.get(OverlapLists[i]) << ", "
+       << RegSeqs.get(SubRegLists[i]) << ", "
+       << RegSeqs.get(Reg->getSuperRegs()) << " },\n";
   }
   OS << "};\n\n";      // End of register descriptors...
 
@@ -464,8 +454,7 @@ 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 << "RegOverlaps, "
-     << TargetName << "SubRegsSet, " << TargetName << "SuperRegsSet, ";
+     << RegisterClasses.size() << ", " << TargetName << "RegLists, ";
   if (SubRegIndices.size() != 0)
     OS << "(uint16_t*)" << TargetName << "SubRegTable, "
        << SubRegIndices.size() << ");\n\n";
@@ -563,25 +552,14 @@ RegisterInfoEmitter::runTargetDesc(raw_ostream &OS, CodeGenTarget &Target,
       AllocatableRegs.insert(Order.begin(), Order.end());
   }
 
-  OS << "namespace {     // Register classes...\n";
-
-  // Emit the ValueType arrays for each RegisterClass
-  for (unsigned rc = 0, e = RegisterClasses.size(); rc != e; ++rc) {
-    const CodeGenRegisterClass &RC = *RegisterClasses[rc];
-
-    // Give the register class a legal C name if it's anonymous.
-    std::string Name = RC.getName() + "VTs";
-
-    // Emit the register list now.
-    OS << "  // " << Name
-       << " Register Class Value Types...\n"
-       << "  const MVT::SimpleValueType " << Name
-       << "[] = {\n    ";
-    for (unsigned i = 0, e = RC.VTs.size(); i != e; ++i)
-      OS << getEnumName(RC.VTs[i]) << ", ";
-    OS << "MVT::Other\n  };\n\n";
-  }
-  OS << "}  // end anonymous namespace\n\n";
+  // Build a shared array of value types.
+  SequenceToOffsetTable<std::vector<MVT::SimpleValueType> > VTSeqs;
+  for (unsigned rc = 0, e = RegisterClasses.size(); rc != e; ++rc)
+    VTSeqs.add(RegisterClasses[rc]->VTs);
+  VTSeqs.layout();
+  OS << "\nstatic const MVT::SimpleValueType VTLists[] = {\n";
+  VTSeqs.emit(OS, printSimpleValueType, "MVT::Other");
+  OS << "};\n";
 
   // Now that all of the structs have been emitted, emit the instances.
   if (!RegisterClasses.empty()) {
@@ -708,7 +686,7 @@ RegisterInfoEmitter::runTargetDesc(raw_ostream &OS, CodeGenTarget &Target,
          << RegisterClasses[i]->getName() << "RegClass = {\n    "
          << '&' << Target.getName() << "MCRegisterClasses[" << RC.getName()
          << "RegClassID],\n    "
-         << RC.getName() << "VTs,\n    "
+         << "VTLists + " << VTSeqs.get(RC.VTs) << ",\n    "
          << RC.getName() << "SubclassMask,\n    ";
       if (RC.getSuperClasses().empty())
         OS << "NullRegClasses,\n    ";
@@ -889,9 +867,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 << "RegOverlaps[];\n";
-  OS << "extern const uint16_t " << TargetName << "SubRegsSet[];\n";
-  OS << "extern const uint16_t " << TargetName << "SuperRegsSet[];\n";
+  OS << "extern const uint16_t " << TargetName << "RegLists[];\n";
   if (SubRegIndices.size() != 0)
     OS << "extern const uint16_t *get" << TargetName
        << "SubRegTable();\n";
@@ -904,8 +880,7 @@ RegisterInfoEmitter::runTargetDesc(raw_ostream &OS, CodeGenTarget &Target,
      << "  InitMCRegisterInfo(" << TargetName << "RegDesc, "
      << Regs.size()+1 << ", RA,\n                     " << TargetName
      << "MCRegisterClasses, " << RegisterClasses.size() << ",\n"
-     << "                     " << TargetName << "RegOverlaps, "
-     << TargetName << "SubRegsSet, " << TargetName << "SuperRegsSet,\n"
+     << "                     " << TargetName << "RegLists,\n"
      << "                     ";
   if (SubRegIndices.size() != 0)
     OS << "get" << TargetName << "SubRegTable(), "
diff --git a/utils/TableGen/SequenceToOffsetTable.h b/utils/TableGen/SequenceToOffsetTable.h
index 26e705841f..09dccbb108 100644
--- a/utils/TableGen/SequenceToOffsetTable.h
+++ b/utils/TableGen/SequenceToOffsetTable.h
@@ -103,7 +103,9 @@ public:
 
   /// emit - Print out the table as the body of an array initializer.
   /// Use the Print function to print elements.
-  void emit(raw_ostream &OS, void (*Print)(raw_ostream&, ElemT)) const {
+  void emit(raw_ostream &OS,
+            void (*Print)(raw_ostream&, ElemT),
+            const char *Term = "0") const {
     assert(Entries && "Call layout() before emit()");
     for (typename SeqMap::const_iterator I = Seqs.begin(), E = Seqs.end();
          I != E; ++I) {
@@ -113,7 +115,7 @@ public:
         Print(OS, *SI);
         OS << ", ";
       }
-      OS << "0,\n";
+      OS << Term << ",\n";
     }
   }
 };