TableGen: Fix subreg composition/concatenation

[MatzeB]

Summary

This fixes 2 problems in subregister hierarchies with multiple levels
and tuples:

1. For bigger tuples computing secondary subregs would miss 2nd

order effects. In the test case a register like S10_S11_S12_S13_S14
with D5 = S10_S11, D6 = S12_S13 we would correctly compute sub0 = D5,
sub1 = D6 but would miss the fact that we could now form
ssub0_ssub1_ssub2_ssub3 (aka sub0_sub1) = D5_D6. This is fixed by
changing computeSecondarySubRegs() to compute a fixpoint.

2. Fixing 1) exposed a problem where TableGen would create multiple

names for effectively the same subregister index. In the test case
the subregister index sub0 is composed from ssub0 and ssub1, and sub1 is
composed from ssub2 and ssub3. TableGen should not create both sub0_sub1
and ssub0_ssub1_ssub2_ssub3 as infered subregister indexes. This changes
the code to build a transitive closure of the subregister components
before forming new concatenated subregister indexes.

This fix was developed for an out of tree target. For the in-tree
targets the only change is in the register information computed for ARM.
There is a slight chance this fixed/improved some register coalescing
around the QQQQ/QQ register classes there but I couldn't see/provoke any
code generation differences.

[qcolombet]

LGTM.
Nitpicks below, no need to submit a new version.

Thanks

test/TableGen/ConcatenatedSubregs.td

16

Could you add a comment with a drawing of the register hierarchy you describe?
For lazy people like me, it is faster to get what is being represented :).

utils/TableGen/CodeGenRegisters.cpp

130

No brackets for 1 line blocks

496

Could you add messages in the asserts?

504

No brackets for 1 line blocks

test/TableGen/ConcatenatedSubregs.td

+// RUN: llvm-tblgen -gen-register-info-debug-dump -I %p/../../include %s | FileCheck %s
+// Checks that tablegen correctly and completely infers subregister relations.
+include "llvm/Target/Target.td"
+
+class MyReg<string n, list<Register> subregs = []>
+  : Register<n> {
+  let Namespace = "Test";
+  let SubRegs = subregs;
+  let CoveredBySubRegs = 1;
+}
+class MyClass<int size, list<ValueType> types, dag registers>
+  : RegisterClass<"Test", types, size, registers> {
+  let Size = size;
+}
+
+def sub0 : SubRegIndex<32>;
+def sub1 : SubRegIndex<32, 32>;
+def sub2 : SubRegIndex<32, 64>;
+
+def ssub0 : SubRegIndex<16>;
+def ssub1 : SubRegIndex<16, 16>;
+def ssub2 : ComposedSubRegIndex<sub1, ssub0>;
+def ssub3 : ComposedSubRegIndex<sub1, ssub1>;
+def ssub4 : ComposedSubRegIndex<sub2, ssub0>;
+
+def S0 : MyReg<"s0">;
+def S1 : MyReg<"s1">;
+def S2 : MyReg<"s2">;
+def S3 : MyReg<"s3">;
+def S4 : MyReg<"s4">;
+def S5 : MyReg<"s5">;
+def S6 : MyReg<"s6">;
+def S7 : MyReg<"s7">;
+def S8 : MyReg<"s8">;
+def S9 : MyReg<"s9">;
+def S10 : MyReg<"s10">;
+def S11 : MyReg<"s11">;
+def S12 : MyReg<"s12">;
+def S13 : MyReg<"s13">;
+def S14 : MyReg<"s14">;
+def S15 : MyReg<"s15">;
+def SRegs : MyClass<16, [i16], (sequence "S%u", 0, 15)>;
+
+let SubRegIndices = [ssub0, ssub1] in {
+def D0 : MyReg<"d0", [S0, S1]>;
+def D1 : MyReg<"d1", [S2, S3]>;
+def D2 : MyReg<"d2", [S4, S5]>;
+def D3 : MyReg<"d3", [S6, S7]>;
+def D4 : MyReg<"d4", [S8, S9]>;
+def D5 : MyReg<"d5", [S10, S11]>;
+def D6 : MyReg<"d6", [S12, S13]>;
+def D7 : MyReg<"d7", [S14, S15]>;
+}
+def DRegs : MyClass<32, [i32], (sequence "D%u", 0, 7)>;
+
+def Dtup2regs : RegisterTuples<[sub0, sub1],
+                           [(shl DRegs, 0), (shl DRegs, 1)]>;
+def Dtup2 : MyClass<64, [untyped], (add Dtup2regs)>;
+
+def Stup2_odds_regs : RegisterTuples<[ssub0, ssub1],
+                                     [(decimate (shl SRegs, 1), 2),
+                                      (decimate (shl SRegs, 2), 2)]>;
+def Stup2 : MyClass<32, [untyped], (interleave DRegs, Stup2_odds_regs)>;
+
+def Stup5 : RegisterTuples<[ssub0, ssub1, ssub2, ssub3, ssub4], [
+                            (shl SRegs, 0),
+                            (shl SRegs, 1),
+                            (shl SRegs, 2),
+                            (shl SRegs, 3),
+                            (shl SRegs, 4)
+                           ]>;
+
+
+def TestTarget : Target;
+
+// CHECK-LABEL: RegisterClass SRegs:
+// CHECK: CoveredBySubRegs: 1
+// CHECK: Regs: S0 S1 S2 S3 S4 S5 S6 S7 S8 S9 S10 S11 S12 S13 S14 S15
+
+// CHECK-LABEL: RegisterClass Stup2:
+// CHECK: CoveredBySubRegs: 1
+// CHECK: Regs: D0 D1 D2 D3 D4 D5 D6 D7 S1_S2 S3_S4 S5_S6 S7_S8 S9_S10 S11_S12 S13_S14
+// CHECK-LABEL: RegisterClass DRegs:
+
+// CHECK-LABEL: SubRegIndex sub0:
+// CHECK-LABEL: SubRegIndex sub1:
+// CHECK-LABEL: SubRegIndex sub2:
+// Check infered indexes:
+// CHECK: SubRegIndex ssub1_ssub2:
+// CHECK: SubRegIndex ssub3_ssub4:
+// CHECK: SubRegIndex ssub0_ssub1_ssub2_ssub3:
+// CHECK: SubRegIndex ssub1_ssub2_ssub3_ssub4:
+
+// Check that all subregs are generated on some examples
+// CHECK-LABEL: Register D0:
+// CHECK: HasDisjunctSubRegs: 1
+// CHECK-NEXT: SubReg ssub0 = S0
+// CHECK-NEXT: SubReg ssub1 = S1
+
+// CHECK-LABEL: Register S9_S10_S11_S12_S13:
+// CHECK: HasDisjunctSubRegs: 1
+// CHECK-NEXT: SubReg ssub0 = S9
+// CHECK-NEXT: SubReg ssub1 = S10
+// CHECK-NEXT: SubReg ssub2 = S11
+// CHECK-NEXT: SubReg ssub3 = S12
+// CHECK-NEXT: SubReg ssub4 = S13
+// CHECK-NEXT: SubReg sub0 = S9_S10
+// CHECK-NEXT: SubReg sub1 = S11_S12
+// CHECK-NEXT: SubReg ssub1_ssub2 = D5
+// CHECK-NEXT: SubReg ssub3_ssub4 = D6
+// CHECK-NEXT: SubReg ssub1_ssub2_ssub3_ssub4 = D5_D6
+
+// CHECK-LABEL: Register S10_S11_S12_S13_S14:
+// CHECK: HasDisjunctSubRegs: 1
+// CHECK-NEXT: SubReg ssub0 = S10
+// CHECK-NEXT: SubReg ssub1 = S11
+// CHECK-NEXT: SubReg ssub2 = S12
+// CHECK-NEXT: SubReg ssub3 = S13
+// CHECK-NEXT: SubReg ssub4 = S14
+// CHECK-NEXT: SubReg sub0 = D5
+// CHECK-NEXT: SubReg sub1 = D6
+// CHECK-NEXT: SubReg ssub1_ssub2 = S11_S12
+// CHECK-NEXT: SubReg ssub3_ssub4 = S13_S14
+// CHECK-NEXT: SubReg ssub0_ssub1_ssub2_ssub3 = D5_D6

utils/TableGen/CodeGenRegisters.h

namespace llvm {
 
   public:
     uint16_t Size;
     uint16_t Offset;
     const unsigned EnumValue;
     mutable LaneBitmask LaneMask;
     mutable SmallVector<MaskRolPair,1> CompositionLaneMaskTransform;
 
+    /// A list of subregister indexes concatenated resulting in this
+    /// subregister index. This is the reverse of CodeGenRegBank::ConcatIdx.
+    SmallVector<CodeGenSubRegIndex*,4> ConcatenationOf;
+
     // Are all super-registers containing this SubRegIndex covered by their
     // sub-registers?
     bool AllSuperRegsCovered;
 
     CodeGenSubRegIndex(Record *R, unsigned Enum);
     CodeGenSubRegIndex(StringRef N, StringRef Nspace, unsigned Enum);
 
     const std::string &getName() const { return Name; }
public:
     void updateComponents(CodeGenRegBank&);
 
     // Return the map of composites.
     const CompMap &getComposites() const { return Composed; }
 
     // Compute LaneMask from Composed. Return LaneMask.
     LaneBitmask computeLaneMask() const;
 
+    void setConcatenationOf(ArrayRef<CodeGenSubRegIndex*> Parts);
+
+    void computeConcatTransitiveClosure();
+
   private:
     CompMap Composed;
   };
 
   inline bool operator<(const CodeGenSubRegIndex &A,
                         const CodeGenSubRegIndex &B) {
     return A.EnumValue < B.EnumValue;
   }
public:
     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::deque<CodeGenRegister> &getRegisters() { return Registers; }
 
     const StringMap<CodeGenRegister*> &getRegistersByName() {
       return RegistersByName;
     }
 
     // Find a register from its Record def.
     CodeGenRegister *getReg(Record*);

utils/TableGen/CodeGenRegisters.cpp

 #include "llvm/Support/raw_ostream.h"
 #include "llvm/TableGen/Error.h"
 #include "llvm/TableGen/Record.h"
 #include <algorithm>
 #include <cassert>
 #include <cstdint>
 #include <iterator>
 #include <map>
+#include <queue>
 #include <set>
 #include <string>
 #include <tuple>
 #include <utility>
 #include <vector>
 
 using namespace llvm;
 
std::vector<Record*> Parts =
     TheDef->getValueAsListOfDefs("CoveringSubRegIndices");
   if (!Parts.empty()) {
     if (Parts.size() < 2)
       PrintFatalError(TheDef->getLoc(),
                       "CoveredBySubRegs must have two or more entries");
     SmallVector<CodeGenSubRegIndex*, 8> IdxParts;
     for (unsigned i = 0, e = Parts.size(); i != e; ++i)
       IdxParts.push_back(RegBank.getSubRegIdx(Parts[i]));
-    RegBank.addConcatSubRegIndex(IdxParts, this);
+    setConcatenationOf(IdxParts);
   }
 }
 
 LaneBitmask CodeGenSubRegIndex::computeLaneMask() const {
   // Already computed?
   if (LaneMask.any())
     return LaneMask;
 
   // Recursion guard, shouldn't be required.
   LaneMask = LaneBitmask::getAll();
 
   // The lane mask is simply the union of all sub-indices.
   LaneBitmask M;
   for (const auto &C : Composed)
     M |= C.second->computeLaneMask();
   assert(M.any() && "Missing lane mask, sub-register cycle?");
   LaneMask = M;
   return LaneMask;
 }
 
+void CodeGenSubRegIndex::setConcatenationOf(
+    ArrayRef<CodeGenSubRegIndex*> Parts) {
+  if (ConcatenationOf.empty()) {
+    ConcatenationOf.assign(Parts.begin(), Parts.end());
+  } else {
+    assert(std::equal(Parts.begin(), Parts.end(),
+                      ConcatenationOf.begin()) && "parts consistent");
+  }
+}
+
+void CodeGenSubRegIndex::computeConcatTransitiveClosure() {
+  for (SmallVectorImpl<CodeGenSubRegIndex*>::iterator
+       I = ConcatenationOf.begin(); I != ConcatenationOf.end(); /*empty*/) {
+    CodeGenSubRegIndex *SubIdx = *I;
+    SubIdx->computeConcatTransitiveClosure();
+#ifndef NDEBUG
+    for (CodeGenSubRegIndex *SRI : SubIdx->ConcatenationOf)
+      assert(SRI->ConcatenationOf.empty() && "No transitive closure?");
+#endif
+
+    if (SubIdx->ConcatenationOf.empty()) {
+      ++I;
+    } else {
+      I = ConcatenationOf.erase(I);
+      I = ConcatenationOf.insert(I, SubIdx->ConcatenationOf.begin(),
+                                 SubIdx->ConcatenationOf.end());
+      I += SubIdx->ConcatenationOf.size();
+    }
+  }
+}
+
 //===----------------------------------------------------------------------===//
 //                              CodeGenRegister
 //===----------------------------------------------------------------------===//
 
 CodeGenRegister::CodeGenRegister(Record *R, unsigned Enum)
   : TheDef(R),
     EnumValue(Enum),
     CostPerUse(R->getValueAsInt("CostPerUse")),
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]);
+    CodeGenSubRegIndex &Idx = *ExplicitSubRegIndices[i];
+    Idx.setConcatenationOf(Parts);
   }
 
   // Initialize RegUnitList. Because getSubRegs is called recursively, this
   // processes the register hierarchy in postorder.
   //
   // Inherit all sub-register units. It is good enough to look at the explicit
   // sub-registers, the other registers won't contribute any more units.
   for (unsigned i = 0, e = ExplicitSubRegs.size(); i != e; ++i) {

 //
 // 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;
 
+  std::queue<std::pair<CodeGenSubRegIndex*,CodeGenRegister*>> SubRegQueue;
+  for (std::pair<CodeGenSubRegIndex*,CodeGenRegister*> P : SubRegs)
+    SubRegQueue.push(P);
+
   // 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;
+  while (!SubRegQueue.empty()) {
+    CodeGenSubRegIndex *SubRegIdx;
+    const CodeGenRegister *SubReg;
+    std::tie(SubRegIdx, SubReg) = SubRegQueue.front();
+    SubRegQueue.pop();
+
     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 {
+      if (Cand->ExplicitSubRegs.size() == 1)
+        continue;
+      SmallVector<CodeGenSubRegIndex*, 8> Parts;
+      // We know that the first component is (SubRegIdx,SubReg). However we
+      // may still need to split it into smaller subregister parts.
+      assert(Cand->ExplicitSubRegs[0] == SubReg);
+      assert(getSubRegIndex(SubReg) == SubRegIdx);
+      for (CodeGenRegister *SubReg : Cand->ExplicitSubRegs) {
+        if (CodeGenSubRegIndex *SubRegIdx = getSubRegIndex(SubReg)) {
+          if (SubRegIdx->ConcatenationOf.empty()) {
+            Parts.push_back(SubRegIdx);
+          } else {
+            for (CodeGenSubRegIndex *SubIdx : SubRegIdx->ConcatenationOf)
+              Parts.push_back(SubIdx);
+          }
+        } 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)
+      // There is nothing to do if some Cand sub-register is not part of this
+      // register.
+      if (Parts.empty())
         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));
-    }
-  }
+      CodeGenSubRegIndex *Concat = RegBank.getConcatSubRegIndex(Parts);
+      std::pair<CodeGenSubRegIndex*,CodeGenRegister*> NewSubReg =
+          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)
+      if (!SubRegs.insert(NewSubReg).second)
         continue;
 
-    CodeGenSubRegIndex *NewIdx = NewSubRegs[i].first;
-    CodeGenRegister *NewSubReg = NewSubRegs[i].second;
-    SubReg2Idx.insert(std::make_pair(NewSubReg, NewIdx));
+      // We inserted a new subregister.
+      NewSubRegs.push_back(NewSubReg);
+      SubRegQueue.push(NewSubReg);
+      SubReg2Idx.insert(std::make_pair(Cand, Concat));
+    }
   }
 
   // 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) {
for (auto &Reg : Registers)
     RegistersByName.insert(
         std::make_pair(Reg.TheDef->getValueAsString("AsmName"), &Reg));
 
   // Precompute all sub-register maps.
   // This will create Composite entries for all inferred sub-register indices.
   for (auto &Reg : Registers)
     Reg.computeSubRegs(*this);
 
+  // Compute transitive closure of subregister index ConcatenationOf vectors
+  // and initialize ConcatIdx map.
+  for (CodeGenSubRegIndex &SRI : SubRegIndices) {
+    SRI.computeConcatTransitiveClosure();
+    if (!SRI.ConcatenationOf.empty())
+      ConcatIdx.insert(std::make_pair(SRI.ConcatenationOf, &SRI));
+  }
+
   // Infer even more sub-registers by combining leading super-registers.
   for (auto &Reg : Registers)
     if (Reg.CoveredBySubRegs)
       Reg.computeSecondarySubRegs(*this);
 
   // After the sub-register graph is complete, compute the topologically
   // ordered SuperRegs list.
   for (auto &Reg : Registers)
CodeGenRegBank::getCompositeSubRegIndex(CodeGenSubRegIndex *A,
   Comp = createSubRegIndex(Name, A->getNamespace());
   A->addComposite(B, Comp);
   return Comp;
 }
 
 CodeGenSubRegIndex *CodeGenRegBank::
 getConcatSubRegIndex(const SmallVector<CodeGenSubRegIndex *, 8> &Parts) {
   assert(Parts.size() > 1 && "Need two parts to concatenate");
+#ifndef NDEBUG
+  for (CodeGenSubRegIndex *Idx : Parts) {
+    assert(Idx->ConcatenationOf.empty() && "No transitive closure?");
+  }
+#endif
 
   // 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) {
     if (Parts[i]->Offset != (LastOffset + LastSize))
       isContinuous = false;
     LastOffset = Parts[i]->Offset;
     LastSize = Parts[i]->Size;
   }
   Idx = createSubRegIndex(Name, Parts.front()->getNamespace());
   Idx->Size = Size;
   Idx->Offset = isContinuous ? Parts.front()->Offset : -1;
+  Idx->ConcatenationOf.assign(Parts.begin(), Parts.end());
   return Idx;
 }
 
 void CodeGenRegBank::computeComposites() {
   // Keep track of TopoSigs visited. We only need to visit each TopoSig once,
   // and many registers will share TopoSigs on regular architectures.
   BitVector TopoSigs(getNumTopoSigs());