Index: llvm/trunk/test/TableGen/ConcatenatedSubregs.td =================================================================== --- llvm/trunk/test/TableGen/ConcatenatedSubregs.td +++ llvm/trunk/test/TableGen/ConcatenatedSubregs.td @@ -0,0 +1,124 @@ +// RUN: llvm-tblgen -gen-register-info -register-info-debug -I %p/../../include %s -o /dev/null 2>&1 | FileCheck %s +// Checks that tablegen correctly and completely infers subregister relations. +include "llvm/Target/Target.td" + +class MyReg subregs = []> + : Register { + let Namespace = "Test"; + let SubRegs = subregs; + let CoveredBySubRegs = 1; +} +class MyClass 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; +def ssub3 : ComposedSubRegIndex; +def ssub4 : ComposedSubRegIndex; + +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 Index: llvm/trunk/utils/TableGen/CodeGenRegisters.h =================================================================== --- llvm/trunk/utils/TableGen/CodeGenRegisters.h +++ llvm/trunk/utils/TableGen/CodeGenRegisters.h @@ -72,6 +72,10 @@ mutable LaneBitmask LaneMask; mutable SmallVector CompositionLaneMaskTransform; + /// A list of subregister indexes concatenated resulting in this + /// subregister index. This is the reverse of CodeGenRegBank::ConcatIdx. + SmallVector ConcatenationOf; + // Are all super-registers containing this SubRegIndex covered by their // sub-registers? bool AllSuperRegsCovered; @@ -123,6 +127,12 @@ // Compute LaneMask from Composed. Return LaneMask. LaneBitmask computeLaneMask() const; + void setConcatenationOf(ArrayRef Parts); + + /// Replaces subregister indexes in the `ConcatenationOf` list with + /// list of subregisters they are composed of (if any). Do this recursively. + void computeConcatTransitiveClosure(); + private: CompMap Composed; }; @@ -609,12 +619,6 @@ CodeGenSubRegIndex * getConcatSubRegIndex(const SmallVector&); - void - addConcatSubRegIndex(const SmallVector &Parts, - CodeGenSubRegIndex *Idx) { - ConcatIdx.insert(std::make_pair(Parts, Idx)); - } - const std::deque &getRegisters() { return Registers; } const StringMap &getRegistersByName() { Index: llvm/trunk/utils/TableGen/CodeGenRegisters.cpp =================================================================== --- llvm/trunk/utils/TableGen/CodeGenRegisters.cpp +++ llvm/trunk/utils/TableGen/CodeGenRegisters.cpp @@ -36,6 +36,7 @@ #include #include #include +#include #include #include #include @@ -98,7 +99,7 @@ SmallVector IdxParts; for (unsigned i = 0, e = Parts.size(); i != e; ++i) IdxParts.push_back(RegBank.getSubRegIdx(Parts[i])); - RegBank.addConcatSubRegIndex(IdxParts, this); + setConcatenationOf(IdxParts); } } @@ -119,6 +120,37 @@ return LaneMask; } +void CodeGenSubRegIndex::setConcatenationOf( + ArrayRef 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::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 //===----------------------------------------------------------------------===// @@ -369,7 +401,8 @@ 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 @@ -430,14 +463,21 @@ // sub-register relationships that would force a DAG. // void CodeGenRegister::computeSecondarySubRegs(CodeGenRegBank &RegBank) { - // Collect new sub-registers first, add them later. SmallVector NewSubRegs; + std::queue> SubRegQueue; + for (std::pair 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(Leads[i]); @@ -445,41 +485,48 @@ 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 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 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 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) - continue; + 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. @@ -1070,6 +1117,14 @@ 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) @@ -1183,6 +1238,11 @@ CodeGenSubRegIndex *CodeGenRegBank:: getConcatSubRegIndex(const SmallVector &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]; @@ -1208,6 +1268,7 @@ 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; }