From 026dc223aeef2579d63f395007491e37d6cde3a0 Mon Sep 17 00:00:00 2001 From: Jakob Stoklund Olesen Date: Sun, 12 Jun 2011 03:05:52 +0000 Subject: 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 --- utils/TableGen/CodeGenRegisters.cpp | 102 ++++++++++++++++++++++++++++++++- utils/TableGen/CodeGenRegisters.h | 34 +++++++++++ utils/TableGen/RegisterInfoEmitter.cpp | 85 ++++++++++----------------- 3 files changed, 164 insertions(+), 57 deletions(-) (limited to 'utils') 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 &OSet) const { + assert(SubRegsComplete && "Must precompute sub-registers"); + std::vector 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 &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 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 #include #include @@ -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 &OSet) const; + + // List of super-registers in topological order, small to large. + typedef std::vector 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 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 &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, LessRecord> &RegisterSubRegs; - -public: - RegisterSorter(std::map, 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 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, LessRecord >::iterator - I = RegisterAliases.begin(), E = RegisterAliases.end(); I != E; ++I) { - OS << " const unsigned " << I->first->getName() << "_Overlaps[] = { " - << getQualifiedName(I->first) << ", "; - for (std::set::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, 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 SubRegsVector; - for (std::set::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 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, 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 SuperRegsVector; - for (std::set::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"; -- cgit v1.2.3