diff options
Diffstat (limited to 'utils/TableGen/CodeGenRegisters.cpp')
| -rw-r--r-- | utils/TableGen/CodeGenRegisters.cpp | 351 |
1 files changed, 329 insertions, 22 deletions
diff --git a/utils/TableGen/CodeGenRegisters.cpp b/utils/TableGen/CodeGenRegisters.cpp index a4504e4f5e82..1acf3a85b600 100644 --- a/utils/TableGen/CodeGenRegisters.cpp +++ b/utils/TableGen/CodeGenRegisters.cpp @@ -14,6 +14,7 @@ #include "CodeGenRegisters.h" #include "CodeGenTarget.h" +#include "Error.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/StringExtras.h" @@ -72,10 +73,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,11 +140,122 @@ CodeGenRegister::getSubRegs(CodeGenRegBank &RegBank) { return SubRegs; } +void +CodeGenRegister::addSubRegsPreOrder(SetVector<CodeGenRegister*> &OSet) const { + assert(SubRegsComplete && "Must precompute sub-registers"); + std::vector<Record*> 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); + } +} + +//===----------------------------------------------------------------------===// +// RegisterTuples +//===----------------------------------------------------------------------===// + +// A RegisterTuples def is used to generate pseudo-registers from lists of +// sub-registers. We provide a SetTheory expander class that returns the new +// registers. +namespace { +struct TupleExpander : SetTheory::Expander { + void expand(SetTheory &ST, Record *Def, SetTheory::RecSet &Elts) { + std::vector<Record*> Indices = Def->getValueAsListOfDefs("SubRegIndices"); + unsigned Dim = Indices.size(); + ListInit *SubRegs = Def->getValueAsListInit("SubRegs"); + if (Dim != SubRegs->getSize()) + throw TGError(Def->getLoc(), "SubRegIndices and SubRegs size mismatch"); + if (Dim < 2) + throw TGError(Def->getLoc(), "Tuples must have at least 2 sub-registers"); + + // Evaluate the sub-register lists to be zipped. + unsigned Length = ~0u; + SmallVector<SetTheory::RecSet, 4> Lists(Dim); + for (unsigned i = 0; i != Dim; ++i) { + ST.evaluate(SubRegs->getElement(i), Lists[i]); + Length = std::min(Length, unsigned(Lists[i].size())); + } + + if (Length == 0) + return; + + // Precompute some types. + Record *RegisterCl = Def->getRecords().getClass("Register"); + RecTy *RegisterRecTy = new RecordRecTy(RegisterCl); + StringInit *BlankName = new StringInit(""); + + // Zip them up. + for (unsigned n = 0; n != Length; ++n) { + std::string Name; + Record *Proto = Lists[0][n]; + std::vector<Init*> Tuple; + unsigned CostPerUse = 0; + for (unsigned i = 0; i != Dim; ++i) { + Record *Reg = Lists[i][n]; + if (i) Name += '_'; + Name += Reg->getName(); + Tuple.push_back(new DefInit(Reg)); + CostPerUse = std::max(CostPerUse, + unsigned(Reg->getValueAsInt("CostPerUse"))); + } + + // Create a new Record representing the synthesized register. This record + // is only for consumption by CodeGenRegister, it is not added to the + // RecordKeeper. + Record *NewReg = new Record(Name, Def->getLoc(), Def->getRecords()); + Elts.insert(NewReg); + + // Copy Proto super-classes. + for (unsigned i = 0, e = Proto->getSuperClasses().size(); i != e; ++i) + NewReg->addSuperClass(Proto->getSuperClasses()[i]); + + // Copy Proto fields. + for (unsigned i = 0, e = Proto->getValues().size(); i != e; ++i) { + RecordVal RV = Proto->getValues()[i]; + + // Replace the sub-register list with Tuple. + if (RV.getName() == "SubRegs") + RV.setValue(new ListInit(Tuple, RegisterRecTy)); + + // Provide a blank AsmName. MC hacks are required anyway. + if (RV.getName() == "AsmName") + RV.setValue(BlankName); + + // CostPerUse is aggregated from all Tuple members. + if (RV.getName() == "CostPerUse") + RV.setValue(new IntInit(CostPerUse)); + + // Copy fields from the RegisterTuples def. + if (RV.getName() == "SubRegIndices" || + RV.getName() == "CompositeIndices") { + NewReg->addValue(*Def->getValue(RV.getName())); + continue; + } + + // Some fields get their default uninitialized value. + if (RV.getName() == "DwarfNumbers" || + RV.getName() == "DwarfAlias" || + RV.getName() == "Aliases") { + if (const RecordVal *DefRV = RegisterCl->getValue(RV.getName())) + NewReg->addValue(*DefRV); + continue; + } + + // Everything else is copied from Proto. + NewReg->addValue(RV); + } + } + } +}; +} + //===----------------------------------------------------------------------===// // CodeGenRegisterClass //===----------------------------------------------------------------------===// -CodeGenRegisterClass::CodeGenRegisterClass(Record *R) : TheDef(R) { +CodeGenRegisterClass::CodeGenRegisterClass(CodeGenRegBank &RegBank, Record *R) + : TheDef(R) { // Rename anonymous register classes. if (R->getName().size() > 9 && R->getName()[9] == '.') { static unsigned AnonCounter = 0; @@ -149,13 +272,26 @@ CodeGenRegisterClass::CodeGenRegisterClass(Record *R) : TheDef(R) { } assert(!VTs.empty() && "RegisterClass must contain at least one ValueType!"); - std::vector<Record*> RegList = R->getValueAsListOfDefs("MemberList"); - for (unsigned i = 0, e = RegList.size(); i != e; ++i) { - Record *Reg = RegList[i]; - if (!Reg->isSubClassOf("Register")) - throw "Register Class member '" + Reg->getName() + - "' does not derive from the Register class!"; - Elements.push_back(Reg); + // Default allocation order always contains all registers. + Elements = RegBank.getSets().expand(R); + for (unsigned i = 0, e = Elements->size(); i != e; ++i) + Members.insert(RegBank.getReg((*Elements)[i])); + + // Alternative allocation orders may be subsets. + ListInit *Alts = R->getValueAsListInit("AltOrders"); + AltOrders.resize(Alts->size()); + SetTheory::RecSet Order; + for (unsigned i = 0, e = Alts->size(); i != e; ++i) { + RegBank.getSets().evaluate(Alts->getElement(i), Order); + AltOrders[i].append(Order.begin(), Order.end()); + // Verify that all altorder members are regclass members. + while (!Order.empty()) { + CodeGenRegister *Reg = RegBank.getReg(Order.back()); + Order.pop_back(); + if (!contains(Reg)) + throw TGError(R->getLoc(), " AltOrder register " + Reg->getName() + + " is not a class member"); + } } // SubRegClasses is a list<dag> containing (RC, subregindex, ...) dags. @@ -189,8 +325,28 @@ CodeGenRegisterClass::CodeGenRegisterClass(Record *R) : TheDef(R) { SpillAlignment = R->getValueAsInt("Alignment"); CopyCost = R->getValueAsInt("CopyCost"); Allocatable = R->getValueAsBit("isAllocatable"); - MethodBodies = R->getValueAsCode("MethodBodies"); - MethodProtos = R->getValueAsCode("MethodProtos"); + AltOrderSelect = R->getValueAsCode("AltOrderSelect"); +} + +bool CodeGenRegisterClass::contains(const CodeGenRegister *Reg) const { + return Members.count(Reg); +} + +// 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 +// satisfy these conditions: +// +// 1. All RC registers are also in this. +// 2. The RC spill size must not be smaller than our spill size. +// 3. RC spill alignment must be compatible with ours. +// +bool CodeGenRegisterClass::hasSubClass(const CodeGenRegisterClass *RC) const { + return SpillAlignment && RC->SpillAlignment % SpillAlignment == 0 && + SpillSize <= RC->SpillSize && + std::includes(Members.begin(), Members.end(), + RC->Members.begin(), RC->Members.end(), + CodeGenRegister::Less()); } const std::string &CodeGenRegisterClass::getName() const { @@ -202,6 +358,10 @@ const std::string &CodeGenRegisterClass::getName() const { //===----------------------------------------------------------------------===// CodeGenRegBank::CodeGenRegBank(RecordKeeper &Records) : Records(Records) { + // Configure register Sets to understand register classes and tuples. + Sets.addFieldExpander("RegisterClass", "MemberList"); + Sets.addExpander("RegisterTuples", new TupleExpander()); + // Read in the user-defined (named) sub-register indices. // More indices will be synthesized later. SubRegIndices = Records.getAllDerivedDefinitions("SubRegIndex"); @@ -214,18 +374,45 @@ CodeGenRegBank::CodeGenRegBank(RecordKeeper &Records) : Records(Records) { Registers.reserve(Regs.size()); // Assign the enumeration values. for (unsigned i = 0, e = Regs.size(); i != e; ++i) - Registers.push_back(CodeGenRegister(Regs[i], i + 1)); + getReg(Regs[i]); + + // Expand tuples and number the new registers. + std::vector<Record*> Tups = + Records.getAllDerivedDefinitions("RegisterTuples"); + for (unsigned i = 0, e = Tups.size(); i != e; ++i) { + const std::vector<Record*> *TupRegs = Sets.expand(Tups[i]); + for (unsigned j = 0, je = TupRegs->size(); j != je; ++j) + getReg((*TupRegs)[j]); + } + + // Read in register class definitions. + std::vector<Record*> RCs = Records.getAllDerivedDefinitions("RegisterClass"); + if (RCs.empty()) + throw std::string("No 'RegisterClass' subclasses defined!"); + + RegClasses.reserve(RCs.size()); + for (unsigned i = 0, e = RCs.size(); i != e; ++i) + RegClasses.push_back(CodeGenRegisterClass(*this, RCs[i])); } CodeGenRegister *CodeGenRegBank::getReg(Record *Def) { - if (Def2Reg.empty()) - for (unsigned i = 0, e = Registers.size(); i != e; ++i) - Def2Reg[Registers[i].TheDef] = &Registers[i]; - - if (CodeGenRegister *Reg = Def2Reg[Def]) + CodeGenRegister *&Reg = Def2Reg[Def]; + if (Reg) return Reg; + Reg = new CodeGenRegister(Def, Registers.size() + 1); + Registers.push_back(Reg); + return Reg; +} - throw TGError(Def->getLoc(), "Not a known Register!"); +CodeGenRegisterClass *CodeGenRegBank::getRegClass(Record *Def) { + if (Def2RC.empty()) + for (unsigned i = 0, e = RegClasses.size(); i != e; ++i) + Def2RC[RegClasses[i].TheDef] = &RegClasses[i]; + + if (CodeGenRegisterClass *RC = Def2RC[Def]) + return RC; + + throw TGError(Def->getLoc(), "Not a known RegisterClass!"); } Record *CodeGenRegBank::getCompositeSubRegIndex(Record *A, Record *B, @@ -254,11 +441,11 @@ 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); + Registers[i]->getSubRegs(*this); for (unsigned i = 0, e = Registers.size(); i != e; ++i) { - CodeGenRegister *Reg1 = &Registers[i]; - const CodeGenRegister::SubRegMap &SRM1 = Reg1->getSubRegs(*this); + CodeGenRegister *Reg1 = Registers[i]; + 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 +453,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,7 +493,127 @@ 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<const CodeGenRegister*, CodeGenRegister::Set> &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<Record*> 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(); } +/// 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 +/// superset-subset relationship and the same set of types, return the +/// superclass. Otherwise return null. +const CodeGenRegisterClass* +CodeGenRegBank::getRegClassForRegister(Record *R) { + const CodeGenRegister *Reg = getReg(R); + const std::vector<CodeGenRegisterClass> &RCs = getRegClasses(); + const CodeGenRegisterClass *FoundRC = 0; + for (unsigned i = 0, e = RCs.size(); i != e; ++i) { + const CodeGenRegisterClass &RC = RCs[i]; + if (!RC.contains(Reg)) + continue; + + // If this is the first class that contains the register, + // make a note of it and go on to the next class. + if (!FoundRC) { + FoundRC = &RC; + continue; + } + + // If a register's classes have different types, return null. + if (RC.getValueTypes() != FoundRC->getValueTypes()) + return 0; + + // Check to see if the previously found class that contains + // the register is a subclass of the current class. If so, + // prefer the superclass. + if (RC.hasSubClass(FoundRC)) { + FoundRC = &RC; + continue; + } + + // Check to see if the previously found class that contains + // the register is a superclass of the current class. If so, + // prefer the superclass. + if (FoundRC->hasSubClass(&RC)) + continue; + + // Multiple classes, and neither is a superclass of the other. + // Return null. + return 0; + } + return FoundRC; +} |