Teach TableGen to infer missing register classes.

The set of register classes should be closed under sub-register
operations and intersections. That will allow the register allocator to
model combinations of constraints accurately.

This patch implements the easiest form of register class inference:  For
every register class, and for every sub-register SubIdx, the subset of
registers in RC that have a SubIdx sub-register should also be a register
class.

This does create some new register classes for the targets in the tree:

ARM gets a new QQQQPR_with_ssub_0.  This class was omitted from the .td
file on purpose because it only has two registers.  InstrEmitter and
RegisterCoalescer have safeguards against selecting too small register
classes, so it is harmless.

PowerPC gets a G8RC_with_sub_32 class because LR is not a sub_32
sub-register of LR8.  I think that might be an omission?

X86 puts RIP in the GR64 class, and since that register doesn't have
8-bit sub-registers, we get:

  GR64_with_sub_8bit
  GR64_TC_with_sub_8bit
  GR64_NOREX_with_sub_8bit
  GR64_TC_with_sub_8bit_hi

The various CodeGen classes have already been fixed so adding new
register classes should not affect compile time.

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

2 files changed, 194 insertions, 17 deletions

diff --git a/utils/TableGen/CodeGenRegisters.cpp b/utils/TableGen/CodeGenRegisters.cpp
index b3bd81e8a6..b09dfe9482 100644
--- a/utils/TableGen/CodeGenRegisters.cpp
+++ b/utils/TableGen/CodeGenRegisters.cpp
@@ -333,10 +333,71 @@ CodeGenRegisterClass::CodeGenRegisterClass(CodeGenRegBank &RegBank, Record *R)
   AltOrderSelect = R->getValueAsCode("AltOrderSelect");
 }
 
+// Create an inferred register class that was missing from the .td files.
+// Most properties will be inherited from the closest super-class after the
+// class structure has been computed.
+CodeGenRegisterClass::CodeGenRegisterClass(StringRef Name, Key Props)
+  : Members(*Props.Members),
+    TheDef(0),
+    Name(Name),
+    EnumValue(-1),
+    SpillSize(Props.SpillSize),
+    SpillAlignment(Props.SpillAlignment),
+    CopyCost(0),
+    Allocatable(true) {
+}
+
+// Compute inherited propertied for a synthesized register class.
+void CodeGenRegisterClass::inheritProperties(CodeGenRegBank &RegBank) {
+  assert(!getDef() && "Only synthesized classes can inherit properties");
+  assert(!SuperClasses.empty() && "Synthesized class without super class");
+
+  // The last super-class is the smallest one.
+  CodeGenRegisterClass &Super = *SuperClasses.back();
+
+  // Most properties are copied directly.
+  // Exceptions are members, size, and alignment
+  Namespace = Super.Namespace;
+  VTs = Super.VTs;
+  CopyCost = Super.CopyCost;
+  Allocatable = Super.Allocatable;
+  AltOrderSelect = Super.AltOrderSelect;
+
+  // Copy all allocation orders, filter out foreign registers from the larger
+  // super-class.
+  Orders.resize(Super.Orders.size());
+  for (unsigned i = 0, ie = Super.Orders.size(); i != ie; ++i)
+    for (unsigned j = 0, je = Super.Orders[i].size(); j != je; ++j)
+      if (contains(RegBank.getReg(Super.Orders[i][j])))
+        Orders[i].push_back(Super.Orders[i][j]);
+}
+
 bool CodeGenRegisterClass::contains(const CodeGenRegister *Reg) const {
   return Members.count(Reg);
 }
 
+namespace llvm {
+  raw_ostream &operator<<(raw_ostream &OS, const CodeGenRegisterClass::Key &K) {
+    OS << "{ S=" << K.SpillSize << ", A=" << K.SpillAlignment;
+    for (CodeGenRegister::Set::const_iterator I = K.Members->begin(),
+         E = K.Members->end(); I != E; ++I)
+      OS << ", " << (*I)->getName();
+    return OS << " }";
+  }
+}
+
+// This is a simple lexicographical order that can be used to search for sets.
+// It is not the same as the topological order provided by TopoOrderRC.
+bool CodeGenRegisterClass::Key::
+operator<(const CodeGenRegisterClass::Key &B) const {
+  assert(Members && B.Members);
+  if (*Members != *B.Members)
+    return *Members < *B.Members;
+  if (SpillSize != B.SpillSize)
+    return SpillSize < B.SpillSize;
+  return SpillAlignment < B.SpillAlignment;
+}
+
 // Returns true if RC is a strict subclass.
 // RC is a sub-class of this class if it is a valid replacement for any
 // instruction operand where a register of this classis required. It must
@@ -367,10 +428,11 @@ static int TopoOrderRC(const void *PA, const void *PB) {
   if (A == B)
     return 0;
 
-  // Order by descending set size.
-  if (A->getOrder().size() > B->getOrder().size())
+  // Order by descending set size.  Note that the classes' allocation order may
+  // not have been computed yet.  The Members set is always vaild.
+  if (A->getMembers().size() > B->getMembers().size())
     return -1;
-  if (A->getOrder().size() < B->getOrder().size())
+  if (A->getMembers().size() < B->getMembers().size())
     return 1;
 
   // Order by ascending spill size.
@@ -398,8 +460,9 @@ std::string CodeGenRegisterClass::getQualifiedName() const {
 
 // Compute sub-classes of all register classes.
 // Assume the classes are ordered topologically.
-void CodeGenRegisterClass::
-computeSubClasses(ArrayRef<CodeGenRegisterClass*> RegClasses) {
+void CodeGenRegisterClass::computeSubClasses(CodeGenRegBank &RegBank) {
+  ArrayRef<CodeGenRegisterClass*> RegClasses = RegBank.getRegClasses();
+
   // Visit backwards so sub-classes are seen first.
   for (unsigned rci = RegClasses.size(); rci; --rci) {
     CodeGenRegisterClass &RC = *RegClasses[rci - 1];
@@ -432,6 +495,13 @@ computeSubClasses(ArrayRef<CodeGenRegisterClass*> RegClasses) {
       RegClasses[s]->SuperClasses.push_back(RegClasses[rci]);
     }
   }
+
+  // With the class hierarchy in place, let synthesized register classes inherit
+  // properties from their closest super-class. The iteration order here can
+  // propagate properties down multiple levels.
+  for (unsigned rci = 0; rci != RegClasses.size(); ++rci)
+    if (!RegClasses[rci]->getDef())
+      RegClasses[rci]->inheritProperties(RegBank);
 }
 
 //===----------------------------------------------------------------------===//
@@ -466,22 +536,29 @@ CodeGenRegBank::CodeGenRegBank(RecordKeeper &Records) : Records(Records) {
       getReg((*TupRegs)[j]);
   }
 
+  // Precompute all sub-register maps now all the registers are known.
+  // This will create Composite entries for all inferred sub-register indices.
+  for (unsigned i = 0, e = Registers.size(); i != e; ++i)
+    Registers[i]->getSubRegs(*this);
+
   // Read in register class definitions.
   std::vector<Record*> RCs = Records.getAllDerivedDefinitions("RegisterClass");
   if (RCs.empty())
     throw std::string("No 'RegisterClass' subclasses defined!");
 
+  // Allocate user-defined register classes.
   RegClasses.reserve(RCs.size());
-  for (unsigned i = 0, e = RCs.size(); i != e; ++i) {
-    CodeGenRegisterClass *RC = new CodeGenRegisterClass(*this, RCs[i]);
-    RegClasses.push_back(RC);
-    Def2RC[RCs[i]] = RC;
-  }
+  for (unsigned i = 0, e = RCs.size(); i != e; ++i)
+    addToMaps(new CodeGenRegisterClass(*this, RCs[i]));
+
+  // Infer missing classes to create a full algebra.
+  computeInferredRegisterClasses();
+
   // Order register classes topologically and assign enum values.
   array_pod_sort(RegClasses.begin(), RegClasses.end(), TopoOrderRC);
   for (unsigned i = 0, e = RegClasses.size(); i != e; ++i)
     RegClasses[i]->EnumValue = i;
-  CodeGenRegisterClass::computeSubClasses(RegClasses);
+  CodeGenRegisterClass::computeSubClasses(*this);
 }
 
 CodeGenRegister *CodeGenRegBank::getReg(Record *Def) {
@@ -493,6 +570,18 @@ CodeGenRegister *CodeGenRegBank::getReg(Record *Def) {
   return Reg;
 }
 
+void CodeGenRegBank::addToMaps(CodeGenRegisterClass *RC) {
+  RegClasses.push_back(RC);
+
+  if (Record *Def = RC->getDef())
+    Def2RC.insert(std::make_pair(Def, RC));
+
+  // Duplicate classes are rejected by insert().
+  // That's OK, we only care about the properties handled by CGRC::Key.
+  CodeGenRegisterClass::Key K(*RC);
+  Key2RC.insert(std::make_pair(K, RC));
+}
+
 CodeGenRegisterClass *CodeGenRegBank::getRegClass(Record *Def) {
   if (CodeGenRegisterClass *RC = Def2RC[Def])
     return RC;
@@ -522,11 +611,6 @@ unsigned CodeGenRegBank::getSubRegIndexNo(Record *idx) {
 }
 
 void CodeGenRegBank::computeComposites() {
-  // Precompute all sub-register maps. This will create Composite entries for
-  // all inferred sub-register indices.
-  for (unsigned i = 0, e = Registers.size(); i != e; ++i)
-    Registers[i]->getSubRegs(*this);
-
   for (unsigned i = 0, e = Registers.size(); i != e; ++i) {
     CodeGenRegister *Reg1 = Registers[i];
     const CodeGenRegister::SubRegMap &SRM1 = Reg1->getSubRegs();
@@ -655,6 +739,56 @@ void CodeGenRegBank::computeDerivedInfo() {
   computeComposites();
 }
 
+// Infer missing register classes.
+//
+// For every register class RC, make sure that the set of registers in RC with
+// a given SubIxx sub-register form a register class.
+void CodeGenRegBank::computeInferredRegisterClasses() {
+  // When this function is called, the register classes have not been sorted
+  // and assigned EnumValues yet.  That means getSubClasses(),
+  // getSuperClasses(), and hasSubClass() functions are defunct.
+
+  // Map SubRegIndex to register set.
+  typedef std::map<Record*, CodeGenRegister::Set, LessRecord> SubReg2SetMap;
+
+  // Visit all register classes, including the ones being added by the loop.
+  for (unsigned rci = 0; rci != RegClasses.size(); ++rci) {
+    CodeGenRegisterClass &RC = *RegClasses[rci];
+
+    // Compute the set of registers supporting each SubRegIndex.
+    SubReg2SetMap SRSets;
+    for (CodeGenRegister::Set::iterator RI = RC.getMembers().begin(),
+         RE = RC.getMembers().end(); RI != RE; ++RI) {
+      CodeGenRegister::SubRegMap SRM = (*RI)->getSubRegs();
+      for (CodeGenRegister::SubRegMap::iterator I = SRM.begin(), E = SRM.end();
+           I != E; ++I)
+        SRSets[I->first].insert(*RI);
+    }
+
+    // Find matching classes for all SRSets entries.  Iterate in SubRegIndex
+    // numerical order to visit synthetic indices last.
+    for (unsigned sri = 0, sre = SubRegIndices.size(); sri != sre; ++sri) {
+      SubReg2SetMap::const_iterator I = SRSets.find(SubRegIndices[sri]);
+      // Unsupported SubRegIndex. Skip it.
+      if (I == SRSets.end())
+        continue;
+      // In most cases, all RC registers support the SubRegIndex. Skip those.
+      if (I->second.size() == RC.getMembers().size())
+        continue;
+
+      // This is a real subset.  See if we have a matching class.
+      CodeGenRegisterClass::Key K(&I->second, RC.SpillSize, RC.SpillAlignment);
+      RCKeyMap::const_iterator FoundI = Key2RC.find(K);
+      if (FoundI != Key2RC.end())
+        continue;
+
+      // Class doesn't exist.
+      addToMaps(new CodeGenRegisterClass(RC.getName() + "_with_" +
+                                         I->first->getName(), K));
+    }
+  }
+}
+
 /// getRegisterClassForRegister - Find the register class that contains the
 /// specified physical register.  If the register is not in a register class,
 /// return null. If the register is in multiple classes, and the classes have a
diff --git a/utils/TableGen/CodeGenRegisters.h b/utils/TableGen/CodeGenRegisters.h
index 6e8d6c04e0..72c8ac0502 100644
--- a/utils/TableGen/CodeGenRegisters.h
+++ b/utils/TableGen/CodeGenRegisters.h
@@ -70,6 +70,7 @@ namespace llvm {
     struct Less {
       bool operator()(const CodeGenRegister *A,
                       const CodeGenRegister *B) const {
+        assert(A && B);
         return A->EnumValue < B->EnumValue;
       }
     };
@@ -95,6 +96,11 @@ namespace llvm {
     SmallVector<CodeGenRegisterClass*, 4> SuperClasses;
     Record *TheDef;
     std::string Name;
+
+    // For a synthesized class, inherit missing properties from the nearest
+    // super-class.
+    void inheritProperties(CodeGenRegBank&);
+
   public:
     unsigned EnumValue;
     std::string Namespace;
@@ -166,8 +172,36 @@ namespace llvm {
 
     CodeGenRegisterClass(CodeGenRegBank&, Record *R);
 
+    // A key representing the parts of a register class used for forming
+    // sub-classes.  Note the ordering provided by this key is not the same as
+    // the topological order used for the EnumValues.
+    struct Key {
+      const CodeGenRegister::Set *Members;
+      unsigned SpillSize;
+      unsigned SpillAlignment;
+
+      Key(const Key &O)
+        : Members(O.Members),
+          SpillSize(O.SpillSize),
+          SpillAlignment(O.SpillAlignment) {}
+
+      Key(const CodeGenRegister::Set *M, unsigned S = 0, unsigned A = 0)
+        : Members(M), SpillSize(S), SpillAlignment(A) {}
+
+      Key(const CodeGenRegisterClass &RC)
+        : Members(&RC.getMembers()),
+          SpillSize(RC.SpillSize),
+          SpillAlignment(RC.SpillAlignment) {}
+
+      // Lexicographical order of (Members, SpillSize, SpillAlignment).
+      bool operator<(const Key&) const;
+    };
+
+    // Create a non-user defined register class.
+    CodeGenRegisterClass(StringRef Name, Key Props);
+
     // Called by CodeGenRegBank::CodeGenRegBank().
-    static void computeSubClasses(ArrayRef<CodeGenRegisterClass*>);
+    static void computeSubClasses(CodeGenRegBank&);
   };
 
   // CodeGenRegBank - Represent a target's registers and the relations between
@@ -181,8 +215,17 @@ namespace llvm {
     std::vector<CodeGenRegister*> Registers;
     DenseMap<Record*, CodeGenRegister*> Def2Reg;
 
+    // Register classes.
     std::vector<CodeGenRegisterClass*> RegClasses;
     DenseMap<Record*, CodeGenRegisterClass*> Def2RC;
+    typedef std::map<CodeGenRegisterClass::Key, CodeGenRegisterClass*> RCKeyMap;
+    RCKeyMap Key2RC;
+
+    // Add RC to *2RC maps.
+    void addToMaps(CodeGenRegisterClass*);
+
+    // Infer missing register classes.
+    void computeInferredRegisterClasses();
 
     // Composite SubRegIndex instances.
     // Map (SubRegIndex, SubRegIndex) -> SubRegIndex.