Compute lists of sub-regs, super-regs, and overlapping regs.

Besides moving structural computations to CodeGenRegisters.cpp, this
also well-defines the order of these lists:

- Sub-register lists come from a pre-order traversal of the graph
  defined by the SubRegs lists in the .td files.

- Super-register lists are topologically ordered so no register comes
  before any of its sub-registers. When the sub-register graph is not a
  tree, independent super-registers appear in numerical order.

- Lists of overlapping registers are ordered according to register
  number.

This reverses the order of the super-regs lists, but nobody was
depending on that. The previous order of the overlaps lists was odd, and
it may have depended on the precise behavior of std::stable_sort.

The old computations are still there, but will be removed shortly.

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

3 files changed, 164 insertions, 57 deletions

diff --git a/utils/TableGen/CodeGenRegisters.cpp b/utils/TableGen/CodeGenRegisters.cpp
index a4504e4f5e..85834e1217 100644
--- a/utils/TableGen/CodeGenRegisters.cpp
+++ b/utils/TableGen/CodeGenRegisters.cpp
@@ -72,10 +72,21 @@ CodeGenRegister::getSubRegs(CodeGenRegBank &RegBank) {
   for (unsigned i = 0, e = SubList.size(); i != e; ++i) {
     CodeGenRegister *SR = RegBank.getReg(SubList[i]);
     const SubRegMap &Map = SR->getSubRegs(RegBank);
+
+    // Add this as a super-register of SR now all sub-registers are in the list.
+    // This creates a topological ordering, the exact order depends on the
+    // order getSubRegs is called on all registers.
+    SR->SuperRegs.push_back(this);
+
     for (SubRegMap::const_iterator SI = Map.begin(), SE = Map.end(); SI != SE;
-         ++SI)
+         ++SI) {
       if (!SubRegs.insert(*SI).second)
         Orphans.push_back(Orphan(SI->second, Indices[i], SI->first));
+
+      // Noop sub-register indexes are possible, so avoid duplicates.
+      if (SI->second != SR)
+        SI->second->SuperRegs.push_back(this);
+    }
   }
 
   // Process the composites.
@@ -128,6 +139,17 @@ CodeGenRegister::getSubRegs(CodeGenRegBank &RegBank) {
   return SubRegs;
 }
 
+void
+CodeGenRegister::addSubRegsPreOrder(SetVector<CodeGenRegister*> &OSet) const {
+  assert(SubRegsComplete && "Must precompute sub-registers");
+  std::vector<Record*> Indices = TheDef->getValueAsListOfDefs("SubRegIndices");
+  for (unsigned i = 0, e = Indices.size(); i != e; ++i) {
+    CodeGenRegister *SR = SubRegs.find(Indices[i])->second;
+    if (OSet.insert(SR))
+      SR->addSubRegsPreOrder(OSet);
+  }
+}
+
 //===----------------------------------------------------------------------===//
 //                            CodeGenRegisterClass
 //===----------------------------------------------------------------------===//
@@ -258,7 +280,7 @@ void CodeGenRegBank::computeComposites() {
 
   for (unsigned i = 0, e = Registers.size(); i != e; ++i) {
     CodeGenRegister *Reg1 = &Registers[i];
-    const CodeGenRegister::SubRegMap &SRM1 = Reg1->getSubRegs(*this);
+    const CodeGenRegister::SubRegMap &SRM1 = Reg1->getSubRegs();
     for (CodeGenRegister::SubRegMap::const_iterator i1 = SRM1.begin(),
          e1 = SRM1.end(); i1 != e1; ++i1) {
       Record *Idx1 = i1->first;
@@ -266,7 +288,7 @@ void CodeGenRegBank::computeComposites() {
       // Ignore identity compositions.
       if (Reg1 == Reg2)
         continue;
-      const CodeGenRegister::SubRegMap &SRM2 = Reg2->getSubRegs(*this);
+      const CodeGenRegister::SubRegMap &SRM2 = Reg2->getSubRegs();
       // Try composing Idx1 with another SubRegIndex.
       for (CodeGenRegister::SubRegMap::const_iterator i2 = SRM2.begin(),
            e2 = SRM2.end(); i2 != e2; ++i2) {
@@ -306,6 +328,80 @@ void CodeGenRegBank::computeComposites() {
   }
 }
 
+// Compute sets of overlapping registers.
+//
+// The standard set is all super-registers and all sub-registers, but the
+// target description can add arbitrary overlapping registers via the 'Aliases'
+// field. This complicates things, but we can compute overlapping sets using
+// the following rules:
+//
+// 1. The relation overlap(A, B) is reflexive and symmetric but not transitive.
+//
+// 2. overlap(A, B) implies overlap(A, S) for all S in supers(B).
+//
+// Alternatively:
+//
+//    overlap(A, B) iff there exists:
+//    A' in { A, subregs(A) } and B' in { B, subregs(B) } such that:
+//    A' = B' or A' in aliases(B') or B' in aliases(A').
+//
+// Here subregs(A) is the full flattened sub-register set returned by
+// A.getSubRegs() while aliases(A) is simply the special 'Aliases' field in the
+// description of register A.
+//
+// This also implies that registers with a common sub-register are considered
+// overlapping. This can happen when forming register pairs:
+//
+//    P0 = (R0, R1)
+//    P1 = (R1, R2)
+//    P2 = (R2, R3)
+//
+// In this case, we will infer an overlap between P0 and P1 because of the
+// shared sub-register R1. There is no overlap between P0 and P2.
+//
+void CodeGenRegBank::
+computeOverlaps(std::map<const CodeGenRegister*, CodeGenRegister::Set> &Map) {
+  assert(Map.empty());
+
+  // Collect overlaps that don't follow from rule 2.
+  for (unsigned i = 0, e = Registers.size(); i != e; ++i) {
+    CodeGenRegister *Reg = &Registers[i];
+    CodeGenRegister::Set &Overlaps = Map[Reg];
+
+    // Reg overlaps itself.
+    Overlaps.insert(Reg);
+
+    // All super-registers overlap.
+    const CodeGenRegister::SuperRegList &Supers = Reg->getSuperRegs();
+    Overlaps.insert(Supers.begin(), Supers.end());
+
+    // Form symmetrical relations from the special Aliases[] lists.
+    std::vector<Record*> RegList = Reg->TheDef->getValueAsListOfDefs("Aliases");
+    for (unsigned i2 = 0, e2 = RegList.size(); i2 != e2; ++i2) {
+      CodeGenRegister *Reg2 = getReg(RegList[i2]);
+      CodeGenRegister::Set &Overlaps2 = Map[Reg2];
+      const CodeGenRegister::SuperRegList &Supers2 = Reg2->getSuperRegs();
+      // Reg overlaps Reg2 which implies it overlaps supers(Reg2).
+      Overlaps.insert(Reg2);
+      Overlaps.insert(Supers2.begin(), Supers2.end());
+      Overlaps2.insert(Reg);
+      Overlaps2.insert(Supers.begin(), Supers.end());
+    }
+  }
+
+  // Apply rule 2. and inherit all sub-register overlaps.
+  for (unsigned i = 0, e = Registers.size(); i != e; ++i) {
+    CodeGenRegister *Reg = &Registers[i];
+    CodeGenRegister::Set &Overlaps = Map[Reg];
+    const CodeGenRegister::SubRegMap &SRM = Reg->getSubRegs();
+    for (CodeGenRegister::SubRegMap::const_iterator i2 = SRM.begin(),
+         e2 = SRM.end(); i2 != e2; ++i2) {
+      CodeGenRegister::Set &Overlaps2 = Map[i2->second];
+      Overlaps.insert(Overlaps2.begin(), Overlaps2.end());
+    }
+  }
+}
+
 void CodeGenRegBank::computeDerivedInfo() {
   computeComposites();
 }
diff --git a/utils/TableGen/CodeGenRegisters.h b/utils/TableGen/CodeGenRegisters.h
index 09341f00d0..233ceb2769 100644
--- a/utils/TableGen/CodeGenRegisters.h
+++ b/utils/TableGen/CodeGenRegisters.h
@@ -18,6 +18,7 @@
 #include "Record.h"
 #include "llvm/CodeGen/ValueTypes.h"
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SetVector.h"
 #include <cstdlib>
 #include <map>
 #include <string>
@@ -49,9 +50,33 @@ namespace llvm {
       return SubRegs;
     }
 
+    // Add sub-registers to OSet following a pre-order defined by the .td file.
+    void addSubRegsPreOrder(SetVector<CodeGenRegister*> &OSet) const;
+
+    // List of super-registers in topological order, small to large.
+    typedef std::vector<CodeGenRegister*> SuperRegList;
+
+    // Get the list of super-registers.
+    // This is only valid after computeDerivedInfo has visited all registers.
+    const SuperRegList &getSuperRegs() const {
+      assert(SubRegsComplete && "Must precompute sub-registers");
+      return SuperRegs;
+    }
+
+    // Order CodeGenRegister pointers by EnumValue.
+    struct Less {
+      bool operator()(const CodeGenRegister *A, const CodeGenRegister *B) {
+        return A->EnumValue < B->EnumValue;
+      }
+    };
+
+    // Canonically ordered set.
+    typedef std::set<CodeGenRegister*, Less> Set;
+
   private:
     bool SubRegsComplete;
     SubRegMap SubRegs;
+    SuperRegList SuperRegs;
   };
 
 
@@ -158,6 +183,15 @@ namespace llvm {
 
     // Computed derived records such as missing sub-register indices.
     void computeDerivedInfo();
+
+    // Compute full overlap sets for every register. These sets include the
+    // rarely used aliases that are neither sub nor super-registers.
+    //
+    // Map[R1].count(R2) is reflexive and symmetric, but not transitive.
+    //
+    // If R1 is a sub-register of R2, Map[R1] is a subset of Map[R2].
+    void computeOverlaps(std::map<const CodeGenRegister*,
+                                  CodeGenRegister::Set> &Map);
   };
 }
 
diff --git a/utils/TableGen/RegisterInfoEmitter.cpp b/utils/TableGen/RegisterInfoEmitter.cpp
index 5a441e285e..3694aa8a49 100644
--- a/utils/TableGen/RegisterInfoEmitter.cpp
+++ b/utils/TableGen/RegisterInfoEmitter.cpp
@@ -168,26 +168,15 @@ static void addSubSuperReg(Record *R, Record *S,
       addSubSuperReg(R, *I, SubRegs, SuperRegs, Aliases);
 }
 
-class RegisterSorter {
-private:
-  std::map<Record*, std::set<Record*>, LessRecord> &RegisterSubRegs;
-
-public:
-  RegisterSorter(std::map<Record*, std::set<Record*>, LessRecord> &RS)
-    : RegisterSubRegs(RS) {}
-
-  bool operator()(Record *RegA, Record *RegB) {
-    // B is sub-register of A.
-    return RegisterSubRegs.count(RegA) && RegisterSubRegs[RegA].count(RegB);
-  }
-};
-
 // RegisterInfoEmitter::run - Main register file description emitter.
 //
 void RegisterInfoEmitter::run(raw_ostream &OS) {
   CodeGenTarget Target(Records);
   CodeGenRegBank &RegBank = Target.getRegBank();
   RegBank.computeDerivedInfo();
+  std::map<const CodeGenRegister*, CodeGenRegister::Set> Overlaps;
+  RegBank.computeOverlaps(Overlaps);
+
   EmitSourceFileHeader("Register Information Source Fragment", OS);
 
   OS << "namespace llvm {\n\n";
@@ -632,60 +621,48 @@ void RegisterInfoEmitter::run(raw_ostream &OS) {
     OS << "\n\n  // Register Overlap Lists...\n";
 
   // Emit an overlap list for all registers.
-  for (std::map<Record*, std::set<Record*>, LessRecord >::iterator
-         I = RegisterAliases.begin(), E = RegisterAliases.end(); I != E; ++I) {
-    OS << "  const unsigned " << I->first->getName() << "_Overlaps[] = { "
-       << getQualifiedName(I->first) << ", ";
-    for (std::set<Record*>::iterator ASI = I->second.begin(),
-           E = I->second.end(); ASI != E; ++ASI)
-      OS << getQualifiedName(*ASI) << ", ";
+  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 << "  const unsigned " << 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";
   }
 
-  if (!RegisterSubRegs.empty())
-    OS << "\n\n  // Register Sub-registers Sets...\n";
-
   // Emit the empty sub-registers list
   OS << "  const unsigned Empty_SubRegsSet[] = { 0 };\n";
   // Loop over all of the registers which have sub-registers, emitting the
   // sub-registers list to memory.
-  for (std::map<Record*, std::set<Record*>, LessRecord>::iterator
-         I = RegisterSubRegs.begin(), E = RegisterSubRegs.end(); I != E; ++I) {
-   if (I->second.empty())
+  for (unsigned i = 0, e = Regs.size(); i != e; ++i) {
+    const CodeGenRegister &Reg = Regs[i];
+    if (Reg.getSubRegs().empty())
      continue;
-    OS << "  const unsigned " << I->first->getName() << "_SubRegsSet[] = { ";
-    std::vector<Record*> SubRegsVector;
-    for (std::set<Record*>::iterator ASI = I->second.begin(),
-           E = I->second.end(); ASI != E; ++ASI)
-      SubRegsVector.push_back(*ASI);
-    RegisterSorter RS(RegisterSubRegs);
-    std::stable_sort(SubRegsVector.begin(), SubRegsVector.end(), RS);
-    for (unsigned i = 0, e = SubRegsVector.size(); i != e; ++i)
-      OS << getQualifiedName(SubRegsVector[i]) << ", ";
+    // getSubRegs() orders by SubRegIndex. We want a topological order.
+    SetVector<CodeGenRegister*> SR;
+    Reg.addSubRegsPreOrder(SR);
+    OS << "  const unsigned " << Reg.getName() << "_SubRegsSet[] = { ";
+    for (unsigned j = 0, je = SR.size(); j != je; ++j)
+      OS << getQualifiedName(SR[j]->TheDef) << ", ";
     OS << "0 };\n";
   }
 
-  if (!RegisterSuperRegs.empty())
-    OS << "\n\n  // Register Super-registers Sets...\n";
-
   // Emit the empty super-registers list
   OS << "  const unsigned Empty_SuperRegsSet[] = { 0 };\n";
   // Loop over all of the registers which have super-registers, emitting the
   // super-registers list to memory.
-  for (std::map<Record*, std::set<Record*>, LessRecord >::iterator
-         I = RegisterSuperRegs.begin(), E = RegisterSuperRegs.end(); I != E; ++I) {
-    if (I->second.empty())
+  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 << "  const unsigned " << I->first->getName() << "_SuperRegsSet[] = { ";
-
-    std::vector<Record*> SuperRegsVector;
-    for (std::set<Record*>::iterator ASI = I->second.begin(),
-           E = I->second.end(); ASI != E; ++ASI)
-      SuperRegsVector.push_back(*ASI);
-    RegisterSorter RS(RegisterSubRegs);
-    std::stable_sort(SuperRegsVector.begin(), SuperRegsVector.end(), RS);
-    for (unsigned i = 0, e = SuperRegsVector.size(); i != e; ++i)
-      OS << getQualifiedName(SuperRegsVector[i]) << ", ";
+    OS << "  const unsigned " << Reg.getName() << "_SuperRegsSet[] = { ";
+    for (unsigned j = 0, je = SR.size(); j != je; ++j)
+      OS << getQualifiedName(SR[j]->TheDef) << ", ";
     OS << "0 };\n";
   }
 
@@ -698,11 +675,11 @@ void RegisterInfoEmitter::run(raw_ostream &OS) {
     const CodeGenRegister &Reg = Regs[i];
     OS << "    { \"";
     OS << Reg.getName() << "\",\t" << Reg.getName() << "_Overlaps,\t";
-    if (!RegisterSubRegs[Reg.TheDef].empty())
+    if (!Reg.getSubRegs().empty())
       OS << Reg.getName() << "_SubRegsSet,\t";
     else
       OS << "Empty_SubRegsSet,\t";
-    if (!RegisterSuperRegs[Reg.TheDef].empty())
+    if (!Reg.getSuperRegs().empty())
       OS << Reg.getName() << "_SuperRegsSet,\t";
     else
       OS << "Empty_SuperRegsSet,\t";