Compute secondary sub-registers.

The sub-registers explicitly listed in SubRegs in the .td files form a
tree. In a complicated register bank, it is possible to have
sub-register relationships across sub-trees. For example, the ARM NEON
double vector Q0_Q1 is a tree:

  Q0_Q1 = [Q0, Q1],  Q0 = [D0, D1], Q1 = [D2, D3]

But we also define the DPair register D1_D2 = [D1, D2] which is fully
contained in Q0_Q1.

This patch teaches TableGen to find such sub-register relationships, and
assign sub-register indices to them. In the example, TableGen will
create a dsub_1_dsub_2 sub-register index, and add D1_D2 as a
sub-register of Q0_Q1.

This will eventually enable the coalescer to handle copies of skewed
sub-registers.

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

2 files changed, 161 insertions, 3 deletions

diff --git a/utils/TableGen/CodeGenRegisters.cpp b/utils/TableGen/CodeGenRegisters.cpp
index 446c00fa85..94782871c7 100644
--- a/utils/TableGen/CodeGenRegisters.cpp
+++ b/utils/TableGen/CodeGenRegisters.cpp
@@ -98,6 +98,14 @@ void CodeGenRegister::buildObjectGraph(CodeGenRegBank &RegBank) {
     ExplicitSubRegIndices.push_back(RegBank.getSubRegIdx(SRIs[i]));
     ExplicitSubRegs.push_back(RegBank.getReg(SRs[i]));
   }
+
+  // Also compute leading super-registers. Each register has a list of
+  // covered-by-subregs super-registers where it appears as the first explicit
+  // sub-register.
+  //
+  // This is used by computeSecondarySubRegs() to find candidates.
+  if (CoveredBySubRegs && !ExplicitSubRegs.empty())
+    ExplicitSubRegs.front()->LeadingSuperRegs.push_back(this);
 }
 
 const std::string &CodeGenRegister::getName() const {
@@ -332,6 +340,24 @@ CodeGenRegister::computeSubRegs(CodeGenRegBank &RegBank) {
     SubReg2Idx.insert(std::make_pair(SI->second, SI->first));
   }
 
+  // Derive possible names for sub-register concatenations from any explicit
+  // sub-registers. By doing this before computeSecondarySubRegs(), we ensure
+  // that getConcatSubRegIndex() won't invent any concatenated indices that the
+  // user already specified.
+  for (unsigned i = 0, e = ExplicitSubRegs.size(); i != e; ++i) {
+    CodeGenRegister *SR = ExplicitSubRegs[i];
+    if (!SR->CoveredBySubRegs || SR->ExplicitSubRegs.size() <= 1)
+      continue;
+
+    // SR is composed of multiple sub-regs. Find their names in this register.
+    SmallVector<CodeGenSubRegIndex*, 8> Parts;
+    for (unsigned j = 0, e = SR->ExplicitSubRegs.size(); j != e; ++j)
+      Parts.push_back(getSubRegIndex(SR->ExplicitSubRegs[j]));
+
+    // Offer this as an existing spelling for the concatenation of Parts.
+    RegBank.addConcatSubRegIndex(Parts, ExplicitSubRegIndices[i]);
+  }
+
   // Initialize RegUnitList. A register with no subregisters creates its own
   // unit. Otherwise, it inherits all its subregister's units. Because
   // getSubRegs is called recursively, this processes the register hierarchy in
@@ -349,6 +375,88 @@ CodeGenRegister::computeSubRegs(CodeGenRegBank &RegBank) {
   return SubRegs;
 }
 
+// In a register that is covered by its sub-registers, try to find redundant
+// sub-registers. For example:
+//
+//   QQ0 = {Q0, Q1}
+//   Q0 = {D0, D1}
+//   Q1 = {D2, D3}
+//
+// We can infer that D1_D2 is also a sub-register, even if it wasn't named in
+// the register definition.
+//
+// The explicitly specified registers form a tree. This function discovers
+// sub-register relationships that would force a DAG.
+//
+void CodeGenRegister::computeSecondarySubRegs(CodeGenRegBank &RegBank) {
+  // Collect new sub-registers first, add them later.
+  SmallVector<SubRegMap::value_type, 8> NewSubRegs;
+
+  // Look at the leading super-registers of each sub-register. Those are the
+  // candidates for new sub-registers, assuming they are fully contained in
+  // this register.
+  for (SubRegMap::iterator I = SubRegs.begin(), E = SubRegs.end(); I != E; ++I){
+    const CodeGenRegister *SubReg = I->second;
+    const CodeGenRegister::SuperRegList &Leads = SubReg->LeadingSuperRegs;
+    for (unsigned i = 0, e = Leads.size(); i != e; ++i) {
+      CodeGenRegister *Cand = const_cast<CodeGenRegister*>(Leads[i]);
+      // Already got this sub-register?
+      if (Cand == this || getSubRegIndex(Cand))
+        continue;
+      // Check if each component of Cand is already a sub-register.
+      // We know that the first component is I->second, and is present with the
+      // name I->first.
+      SmallVector<CodeGenSubRegIndex*, 8> Parts(1, I->first);
+      assert(!Cand->ExplicitSubRegs.empty() &&
+             "Super-register has no sub-registers");
+      for (unsigned j = 1, e = Cand->ExplicitSubRegs.size(); j != e; ++j) {
+        if (CodeGenSubRegIndex *Idx = getSubRegIndex(Cand->ExplicitSubRegs[j]))
+          Parts.push_back(Idx);
+        else {
+          // Sub-register doesn't exist.
+          Parts.clear();
+          break;
+        }
+      }
+      // If some Cand sub-register is not part of this register, or if Cand only
+      // has one sub-register, there is nothing to do.
+      if (Parts.size() <= 1)
+        continue;
+
+      // Each part of Cand is a sub-register of this. Make the full Cand also
+      // a sub-register with a concatenated sub-register index.
+      CodeGenSubRegIndex *Concat= RegBank.getConcatSubRegIndex(Parts);
+      NewSubRegs.push_back(std::make_pair(Concat, Cand));
+    }
+  }
+
+  // Now add all the new sub-registers.
+  for (unsigned i = 0, e = NewSubRegs.size(); i != e; ++i) {
+    // Don't add Cand if another sub-register is already using the index.
+    if (!SubRegs.insert(NewSubRegs[i]).second)
+      continue;
+
+    CodeGenSubRegIndex *NewIdx = NewSubRegs[i].first;
+    CodeGenRegister *NewSubReg = NewSubRegs[i].second;
+    SubReg2Idx.insert(std::make_pair(NewSubReg, NewIdx));
+    NewSubReg->SuperRegs.push_back(this);
+  }
+
+  // Create sub-register index composition maps for the synthesized indices.
+  for (unsigned i = 0, e = NewSubRegs.size(); i != e; ++i) {
+    CodeGenSubRegIndex *NewIdx = NewSubRegs[i].first;
+    CodeGenRegister *NewSubReg = NewSubRegs[i].second;
+    for (SubRegMap::const_iterator SI = NewSubReg->SubRegs.begin(),
+           SE = NewSubReg->SubRegs.end(); SI != SE; ++SI) {
+      CodeGenSubRegIndex *SubIdx = getSubRegIndex(SI->second);
+      if (!SubIdx)
+        throw TGError(TheDef->getLoc(), "No SubRegIndex for " +
+                      SI->second->getName() + " in " + getName());
+      NewIdx->addComposite(SI->first, SubIdx);
+    }
+  }
+}
+
 void
 CodeGenRegister::addSubRegsPreOrder(SetVector<const CodeGenRegister*> &OSet,
                                     CodeGenRegBank &RegBank) const {
@@ -358,6 +466,11 @@ CodeGenRegister::addSubRegsPreOrder(SetVector<const CodeGenRegister*> &OSet,
     if (OSet.insert(SR))
       SR->addSubRegsPreOrder(OSet, RegBank);
   }
+  // Add any secondary sub-registers that weren't part of the explicit tree.
+  for (SubRegMap::const_iterator I = SubRegs.begin(), E = SubRegs.end();
+       I != E; ++I)
+    if (I->second != this)
+      OSet.insert(I->second);
 }
 
 // Get the sum of this register's unit weights.
@@ -782,6 +895,11 @@ CodeGenRegBank::CodeGenRegBank(RecordKeeper &Records) : Records(Records) {
   for (unsigned i = 0, e = Registers.size(); i != e; ++i)
     Registers[i]->computeSubRegs(*this);
 
+  // Infer even more sub-registers by combining leading super-registers.
+  for (unsigned i = 0, e = Registers.size(); i != e; ++i)
+    if (Registers[i]->CoveredBySubRegs)
+      Registers[i]->computeSecondarySubRegs(*this);
+
   // Native register units are associated with a leaf register. They've all been
   // discovered now.
   NumNativeRegUnits = NumRegUnits;
@@ -875,6 +993,24 @@ CodeGenRegBank::getCompositeSubRegIndex(CodeGenSubRegIndex *A,
   return Comp;
 }
 
+CodeGenSubRegIndex *CodeGenRegBank::
+getConcatSubRegIndex(const SmallVector<CodeGenSubRegIndex*, 8> &Parts) {
+  assert(Parts.size() > 1 && "Need two parts to concatenate");
+
+  // Look for an existing entry.
+  CodeGenSubRegIndex *&Idx = ConcatIdx[Parts];
+  if (Idx)
+    return Idx;
+
+  // None exists, synthesize one.
+  std::string Name = Parts.front()->getName();
+  for (unsigned i = 1, e = Parts.size(); i != e; ++i) {
+    Name += '_';
+    Name += Parts[i]->getName();
+  }
+  return Idx = getSubRegIdx(new Record(Name, SMLoc(), Records));
+}
+
 void CodeGenRegBank::computeComposites() {
   for (unsigned i = 0, e = Registers.size(); i != e; ++i) {
     CodeGenRegister *Reg1 = Registers[i];
diff --git a/utils/TableGen/CodeGenRegisters.h b/utils/TableGen/CodeGenRegisters.h
index 1d0e30f9fb..23cc53932d 100644
--- a/utils/TableGen/CodeGenRegisters.h
+++ b/utils/TableGen/CodeGenRegisters.h
@@ -67,6 +67,7 @@ namespace llvm {
     // Return a conflicting composite, or NULL
     CodeGenSubRegIndex *addComposite(CodeGenSubRegIndex *A,
                                      CodeGenSubRegIndex *B) {
+      assert(A && B);
       std::pair<CompMap::iterator, bool> Ins =
         Composed.insert(std::make_pair(A, B));
       return (Ins.second || Ins.first->second == B) ? 0 : Ins.first->second;
@@ -108,6 +109,9 @@ namespace llvm {
     // This includes unique entries for all sub-sub-registers.
     const SubRegMap &computeSubRegs(CodeGenRegBank&);
 
+    // Compute extra sub-registers by combining the existing sub-registers.
+    void computeSecondarySubRegs(CodeGenRegBank&);
+
     const SubRegMap &getSubRegs() const {
       assert(SubRegsComplete && "Must precompute sub-registers");
       return SubRegs;
@@ -123,11 +127,11 @@ namespace llvm {
       return SubReg2Idx.lookup(Reg);
     }
 
-    // List of super-registers in topological order, small to large.
     typedef std::vector<const CodeGenRegister*> SuperRegList;
 
-    // Get the list of super-registers. This is valid after getSubReg
-    // visits all registers during RegBank construction.
+    // Get the list of super-registers in topological order, small to large.
+    // This is valid after computeSubRegs visits all registers during RegBank
+    // construction.
     const SuperRegList &getSuperRegs() const {
       assert(SubRegsComplete && "Must precompute sub-registers");
       return SuperRegs;
@@ -170,6 +174,9 @@ namespace llvm {
     SmallVector<CodeGenSubRegIndex*, 8> ExplicitSubRegIndices;
     SmallVector<CodeGenRegister*, 8> ExplicitSubRegs;
 
+    // Super-registers where this is the first explicit sub-register.
+    SuperRegList LeadingSuperRegs;
+
     SubRegMap SubRegs;
     SuperRegList SuperRegs;
     DenseMap<const CodeGenRegister*, CodeGenSubRegIndex*> SubReg2Idx;
@@ -349,6 +356,10 @@ namespace llvm {
     DenseMap<Record*, CodeGenSubRegIndex*> Def2SubRegIdx;
     unsigned NumNamedIndices;
 
+    typedef std::map<SmallVector<CodeGenSubRegIndex*, 8>,
+                     CodeGenSubRegIndex*> ConcatIdxMap;
+    ConcatIdxMap ConcatIdx;
+
     // Registers.
     std::vector<CodeGenRegister*> Registers;
     DenseMap<Record*, CodeGenRegister*> Def2Reg;
@@ -419,6 +430,17 @@ namespace llvm {
     CodeGenSubRegIndex *getCompositeSubRegIndex(CodeGenSubRegIndex *A,
                                                 CodeGenSubRegIndex *B);
 
+    // Find or create a sub-register index representing the concatenation of
+    // non-overlapping sibling indices.
+    CodeGenSubRegIndex *
+      getConcatSubRegIndex(const SmallVector<CodeGenSubRegIndex*, 8>&);
+
+    void
+    addConcatSubRegIndex(const SmallVector<CodeGenSubRegIndex*, 8> &Parts,
+                         CodeGenSubRegIndex *Idx) {
+      ConcatIdx.insert(std::make_pair(Parts, Idx));
+    }
+
     const std::vector<CodeGenRegister*> &getRegisters() { return Registers; }
 
     // Find a register from its Record def.