X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=utils%2FTableGen%2FCodeGenRegisters.cpp;h=8099f134fd0ed0d6b0e0c766450f9be92f9b86ff;hb=049ffbbdf2a43d5529cb56b6bb696d20d28ff217;hp=9d72d0d4bd6f286dbccc13778689735810ab3b2e;hpb=2275cfd75b65ede0f46f3cf914e76a38daf96417;p=oota-llvm.git diff --git a/utils/TableGen/CodeGenRegisters.cpp b/utils/TableGen/CodeGenRegisters.cpp index 9d72d0d4bd6..8099f134fd0 100644 --- a/utils/TableGen/CodeGenRegisters.cpp +++ b/utils/TableGen/CodeGenRegisters.cpp @@ -19,10 +19,13 @@ #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/StringExtras.h" #include "llvm/ADT/Twine.h" +#include "llvm/Support/Debug.h" #include "llvm/TableGen/Error.h" using namespace llvm; +#define DEBUG_TYPE "regalloc-emitter" + //===----------------------------------------------------------------------===// // CodeGenSubRegIndex //===----------------------------------------------------------------------===// @@ -32,12 +35,14 @@ CodeGenSubRegIndex::CodeGenSubRegIndex(Record *R, unsigned Enum) Name = R->getName(); if (R->getValue("Namespace")) Namespace = R->getValueAsString("Namespace"); + Size = R->getValueAsInt("Size"); + Offset = R->getValueAsInt("Offset"); } CodeGenSubRegIndex::CodeGenSubRegIndex(StringRef N, StringRef Nspace, unsigned Enum) - : TheDef(0), Name(N), Namespace(Nspace), EnumValue(Enum), - LaneMask(0), AllSuperRegsCovered(true) { + : TheDef(nullptr), Name(N), Namespace(Nspace), Size(-1), Offset(-1), + EnumValue(Enum), LaneMask(0), AllSuperRegsCovered(true) { } std::string CodeGenSubRegIndex::getQualifiedName() const { @@ -69,7 +74,7 @@ void CodeGenSubRegIndex::updateComponents(CodeGenRegBank &RegBank) { if (!Parts.empty()) { if (Parts.size() < 2) PrintFatalError(TheDef->getLoc(), - "CoveredBySubRegs must have two or more entries"); + "CoveredBySubRegs must have two or more entries"); SmallVector IdxParts; for (unsigned i = 0, e = Parts.size(); i != e; ++i) IdxParts.push_back(RegBank.getSubRegIdx(Parts[i])); @@ -545,7 +550,7 @@ unsigned CodeGenRegister::getWeight(const CodeGenRegBank &RegBank) const { // registers. namespace { struct TupleExpander : SetTheory::Expander { - void expand(SetTheory &ST, Record *Def, SetTheory::RecSet &Elts) { + void expand(SetTheory &ST, Record *Def, SetTheory::RecSet &Elts) override { std::vector Indices = Def->getValueAsListOfDefs("SubRegIndices"); unsigned Dim = Indices.size(); ListInit *SubRegs = Def->getValueAsListInit("SubRegs"); @@ -707,7 +712,7 @@ CodeGenRegisterClass::CodeGenRegisterClass(CodeGenRegBank &RegBank, Record *R) unsigned Size = R->getValueAsInt("Size"); Namespace = R->getValueAsString("Namespace"); - SpillSize = Size ? Size : EVT(VTs[0]).getSizeInBits(); + SpillSize = Size ? Size : MVT(VTs[0]).getSizeInBits(); SpillAlignment = R->getValueAsInt("Alignment"); CopyCost = R->getValueAsInt("CopyCost"); Allocatable = R->getValueAsBit("isAllocatable"); @@ -720,7 +725,7 @@ CodeGenRegisterClass::CodeGenRegisterClass(CodeGenRegBank &RegBank, Record *R) CodeGenRegisterClass::CodeGenRegisterClass(CodeGenRegBank &RegBank, StringRef Name, Key Props) : Members(*Props.Members), - TheDef(0), + TheDef(nullptr), Name(Name), TopoSigs(RegBank.getNumTopoSigs()), EnumValue(-1), @@ -777,11 +782,8 @@ namespace llvm { bool CodeGenRegisterClass::Key:: operator<(const CodeGenRegisterClass::Key &B) const { assert(Members && B.Members); - if (*Members != *B.Members) - return *Members < *B.Members; - if (SpillSize != B.SpillSize) - return SpillSize < B.SpillSize; - return SpillAlignment < B.SpillAlignment; + return std::tie(*Members, SpillSize, SpillAlignment) < + std::tie(*B.Members, B.SpillSize, B.SpillAlignment); } // Returns true if RC is a strict subclass. @@ -808,9 +810,10 @@ static bool testSubClass(const CodeGenRegisterClass *A, /// Register classes with the same registers, spill size, and alignment form a /// clique. They will be ordered alphabetically. /// -static int TopoOrderRC(const void *PA, const void *PB) { - const CodeGenRegisterClass *A = *(const CodeGenRegisterClass* const*)PA; - const CodeGenRegisterClass *B = *(const CodeGenRegisterClass* const*)PB; +static int TopoOrderRC(CodeGenRegisterClass *const *PA, + CodeGenRegisterClass *const *PB) { + const CodeGenRegisterClass *A = *PA; + const CodeGenRegisterClass *B = *PB; if (A == B) return 0; @@ -936,7 +939,7 @@ CodeGenRegBank::CodeGenRegBank(RecordKeeper &Records) { // Read in the register definitions. std::vector Regs = Records.getAllDerivedDefinitions("Register"); - std::sort(Regs.begin(), Regs.end(), LessRecord()); + std::sort(Regs.begin(), Regs.end(), LessRecordRegister()); Registers.reserve(Regs.size()); // Assign the enumeration values. for (unsigned i = 0, e = Regs.size(); i != e; ++i) @@ -945,10 +948,16 @@ CodeGenRegBank::CodeGenRegBank(RecordKeeper &Records) { // Expand tuples and number the new registers. std::vector Tups = Records.getAllDerivedDefinitions("RegisterTuples"); + + std::vector TupRegsCopy; for (unsigned i = 0, e = Tups.size(); i != e; ++i) { const std::vector *TupRegs = Sets.expand(Tups[i]); - for (unsigned j = 0, je = TupRegs->size(); j != je; ++j) - getReg((*TupRegs)[j]); + TupRegsCopy.reserve(TupRegs->size()); + TupRegsCopy.assign(TupRegs->begin(), TupRegs->end()); + std::sort(TupRegsCopy.begin(), TupRegsCopy.end(), LessRecordRegister()); + for (unsigned j = 0, je = TupRegsCopy.size(); j != je; ++j) + getReg((TupRegsCopy)[j]); + TupRegsCopy.clear(); } // Now all the registers are known. Build the object graph of explicit @@ -984,7 +993,7 @@ CodeGenRegBank::CodeGenRegBank(RecordKeeper &Records) { // Read in register class definitions. std::vector RCs = Records.getAllDerivedDefinitions("RegisterClass"); if (RCs.empty()) - PrintFatalError(std::string("No 'RegisterClass' subclasses defined!")); + PrintFatalError("No 'RegisterClass' subclasses defined!"); // Allocate user-defined register classes. RegClasses.reserve(RCs.size()); @@ -1080,7 +1089,7 @@ CodeGenRegBank::getCompositeSubRegIndex(CodeGenSubRegIndex *A, } CodeGenSubRegIndex *CodeGenRegBank:: -getConcatSubRegIndex(const SmallVector &Parts) { +getConcatSubRegIndex(const SmallVector &Parts) { assert(Parts.size() > 1 && "Need two parts to concatenate"); // Look for an existing entry. @@ -1090,11 +1099,24 @@ getConcatSubRegIndex(const SmallVector &Parts) { // None exists, synthesize one. std::string Name = Parts.front()->getName(); + // Determine whether all parts are contiguous. + bool isContinuous = true; + unsigned Size = Parts.front()->Size; + unsigned LastOffset = Parts.front()->Offset; + unsigned LastSize = Parts.front()->Size; for (unsigned i = 1, e = Parts.size(); i != e; ++i) { Name += '_'; Name += Parts[i]->getName(); + Size += Parts[i]->Size; + if (Parts[i]->Offset != (LastOffset + LastSize)) + isContinuous = false; + LastOffset = Parts[i]->Offset; + LastSize = Parts[i]->Size; } - return Idx = createSubRegIndex(Name, Parts.front()->getNamespace()); + Idx = createSubRegIndex(Name, Parts.front()->getNamespace()); + Idx->Size = Size; + Idx->Offset = isContinuous ? Parts.front()->Offset : -1; + return Idx; } void CodeGenRegBank::computeComposites() { @@ -1246,7 +1268,7 @@ static void computeUberSets(std::vector &UberSets, assert(USetID && "register number 0 is invalid"); AllocatableRegs.insert((*Regs.begin())->EnumValue); - for (CodeGenRegister::Set::const_iterator I = llvm::next(Regs.begin()), + for (CodeGenRegister::Set::const_iterator I = std::next(Regs.begin()), E = Regs.end(); I != E; ++I) { AllocatableRegs.insert((*I)->EnumValue); UberSetIDs.join(USetID, (*I)->EnumValue); @@ -1286,11 +1308,11 @@ static void computeUberSets(std::vector &UberSets, static void computeUberWeights(std::vector &UberSets, CodeGenRegBank &RegBank) { // Skip the first unallocatable set. - for (std::vector::iterator I = llvm::next(UberSets.begin()), + for (std::vector::iterator I = std::next(UberSets.begin()), E = UberSets.end(); I != E; ++I) { // Initialize all unit weights in this set, and remember the max units/reg. - const CodeGenRegister *Reg = 0; + const CodeGenRegister *Reg = nullptr; unsigned MaxWeight = 0, Weight = 0; for (RegUnitIterator UnitI(I->Regs); UnitI.isValid(); ++UnitI) { if (Reg != UnitI.getReg()) { @@ -1308,9 +1330,18 @@ static void computeUberWeights(std::vector &UberSets, } if (Weight > MaxWeight) MaxWeight = Weight; - - // Update the set weight. - I->Weight = MaxWeight; + if (I->Weight != MaxWeight) { + DEBUG( + dbgs() << "UberSet " << I - UberSets.begin() << " Weight " << MaxWeight; + for (CodeGenRegister::Set::iterator + UnitI = I->Regs.begin(), UnitE = I->Regs.end(); + UnitI != UnitE; ++UnitI) { + dbgs() << " " << (*UnitI)->getName(); + } + dbgs() << "\n"); + // Update the set weight. + I->Weight = MaxWeight; + } // Find singular determinants. for (CodeGenRegister::Set::iterator RegI = I->Regs.begin(), @@ -1437,7 +1468,23 @@ static bool isRegUnitSubSet(const std::vector &RUSubSet, RUSubSet.begin(), RUSubSet.end()); } -// Iteratively prune unit sets. +/// Iteratively prune unit sets. Prune subsets that are close to the superset, +/// but with one or two registers removed. We occasionally have registers like +/// APSR and PC thrown in with the general registers. We also see many +/// special-purpose register subsets, such as tail-call and Thumb +/// encodings. Generating all possible overlapping sets is combinatorial and +/// overkill for modeling pressure. Ideally we could fix this statically in +/// tablegen by (1) having the target define register classes that only include +/// the allocatable registers and marking other classes as non-allocatable and +/// (2) having a way to mark special purpose classes as "don't-care" classes for +/// the purpose of pressure. However, we make an attempt to handle targets that +/// are not nicely defined by merging nearly identical register unit sets +/// statically. This generates smaller tables. Then, dynamically, we adjust the +/// set limit by filtering the reserved registers. +/// +/// Merge sets only if the units have the same weight. For example, on ARM, +/// Q-tuples with ssub index 0 include all S regs but also include D16+. We +/// should not expand the S set to include D regs. void CodeGenRegBank::pruneUnitSets() { assert(RegClassUnitSets.empty() && "this invalidates RegClassUnitSets"); @@ -1451,9 +1498,14 @@ void CodeGenRegBank::pruneUnitSets() { if (SuperIdx == SubIdx) continue; + unsigned UnitWeight = RegUnits[SubSet.Units[0]].Weight; const RegUnitSet &SuperSet = RegUnitSets[SuperIdx]; if (isRegUnitSubSet(SubSet.Units, SuperSet.Units) - && (SubSet.Units.size() + 3 > SuperSet.Units.size())) { + && (SubSet.Units.size() + 3 > SuperSet.Units.size()) + && UnitWeight == RegUnits[SuperSet.Units[0]].Weight + && UnitWeight == RegUnits[SuperSet.Units.back()].Weight) { + DEBUG(dbgs() << "UnitSet " << SubIdx << " subsumed by " << SuperIdx + << "\n"); break; } } @@ -1478,6 +1530,7 @@ void CodeGenRegBank::pruneUnitSets() { // RegisterInfoEmitter will map each RegClass to its RegUnitClass and any // RegUnitSet that is a superset of that RegUnitClass. void CodeGenRegBank::computeRegUnitSets() { + assert(RegUnitSets.empty() && "dirty RegUnitSets"); // Compute a unique RegUnitSet for each RegClass. const ArrayRef &RegClasses = getRegClasses(); @@ -1496,13 +1549,36 @@ void CodeGenRegBank::computeRegUnitSets() { // Find an existing RegUnitSet. std::vector::const_iterator SetI = findRegUnitSet(RegUnitSets, RegUnitSets.back()); - if (SetI != llvm::prior(RegUnitSets.end())) + if (SetI != std::prev(RegUnitSets.end())) RegUnitSets.pop_back(); } + DEBUG(dbgs() << "\nBefore pruning:\n"; + for (unsigned USIdx = 0, USEnd = RegUnitSets.size(); + USIdx < USEnd; ++USIdx) { + dbgs() << "UnitSet " << USIdx << " " << RegUnitSets[USIdx].Name + << ":"; + ArrayRef Units = RegUnitSets[USIdx].Units; + for (unsigned i = 0, e = Units.size(); i < e; ++i) + dbgs() << " " << RegUnits[Units[i]].Roots[0]->getName(); + dbgs() << "\n"; + }); + // Iteratively prune unit sets. pruneUnitSets(); + DEBUG(dbgs() << "\nBefore union:\n"; + for (unsigned USIdx = 0, USEnd = RegUnitSets.size(); + USIdx < USEnd; ++USIdx) { + dbgs() << "UnitSet " << USIdx << " " << RegUnitSets[USIdx].Name + << ":"; + ArrayRef Units = RegUnitSets[USIdx].Units; + for (unsigned i = 0, e = Units.size(); i < e; ++i) + dbgs() << " " << RegUnits[Units[i]].Roots[0]->getName(); + dbgs() << "\n"; + } + dbgs() << "\nUnion sets:\n"); + // Iterate over all unit sets, including new ones added by this loop. unsigned NumRegUnitSubSets = RegUnitSets.size(); for (unsigned Idx = 0, EndIdx = RegUnitSets.size(); Idx != EndIdx; ++Idx) { @@ -1538,14 +1614,33 @@ void CodeGenRegBank::computeRegUnitSets() { // Find an existing RegUnitSet, or add the union to the unique sets. std::vector::const_iterator SetI = findRegUnitSet(RegUnitSets, RegUnitSets.back()); - if (SetI != llvm::prior(RegUnitSets.end())) + if (SetI != std::prev(RegUnitSets.end())) RegUnitSets.pop_back(); + else { + DEBUG(dbgs() << "UnitSet " << RegUnitSets.size()-1 + << " " << RegUnitSets.back().Name << ":"; + ArrayRef Units = RegUnitSets.back().Units; + for (unsigned i = 0, e = Units.size(); i < e; ++i) + dbgs() << " " << RegUnits[Units[i]].Roots[0]->getName(); + dbgs() << "\n";); + } } } // Iteratively prune unit sets after inferring supersets. pruneUnitSets(); + DEBUG(dbgs() << "\n"; + for (unsigned USIdx = 0, USEnd = RegUnitSets.size(); + USIdx < USEnd; ++USIdx) { + dbgs() << "UnitSet " << USIdx << " " << RegUnitSets[USIdx].Name + << ":"; + ArrayRef Units = RegUnitSets[USIdx].Units; + for (unsigned i = 0, e = Units.size(); i < e; ++i) + dbgs() << " " << RegUnits[Units[i]].Roots[0]->getName(); + dbgs() << "\n"; + }); + // For each register class, list the UnitSets that are supersets. RegClassUnitSets.resize(NumRegClasses); for (unsigned RCIdx = 0, RCEnd = NumRegClasses; RCIdx != RCEnd; ++RCIdx) { @@ -1553,19 +1648,27 @@ void CodeGenRegBank::computeRegUnitSets() { continue; // Recompute the sorted list of units in this class. - std::vector RegUnits; - RegClasses[RCIdx]->buildRegUnitSet(RegUnits); + std::vector RCRegUnits; + RegClasses[RCIdx]->buildRegUnitSet(RCRegUnits); // Don't increase pressure for unallocatable regclasses. - if (RegUnits.empty()) + if (RCRegUnits.empty()) continue; + DEBUG(dbgs() << "RC " << RegClasses[RCIdx]->getName() << " Units: \n"; + for (unsigned i = 0, e = RCRegUnits.size(); i < e; ++i) + dbgs() << RegUnits[RCRegUnits[i]].getRoots()[0]->getName() << " "; + dbgs() << "\n UnitSetIDs:"); + // Find all supersets. for (unsigned USIdx = 0, USEnd = RegUnitSets.size(); USIdx != USEnd; ++USIdx) { - if (isRegUnitSubSet(RegUnits, RegUnitSets[USIdx].Units)) + if (isRegUnitSubSet(RCRegUnits, RegUnitSets[USIdx].Units)) { + DEBUG(dbgs() << " " << USIdx); RegClassUnitSets[RCIdx].push_back(USIdx); + } } + DEBUG(dbgs() << "\n"); assert(!RegClassUnitSets[RCIdx].empty() && "missing unit set for regclass"); } @@ -1610,6 +1713,24 @@ void CodeGenRegBank::computeDerivedInfo() { // Compute a unique set of RegUnitSets. One for each RegClass and inferred // supersets for the union of overlapping sets. computeRegUnitSets(); + + // Get the weight of each set. + for (unsigned Idx = 0, EndIdx = RegUnitSets.size(); Idx != EndIdx; ++Idx) + RegUnitSets[Idx].Weight = getRegUnitSetWeight(RegUnitSets[Idx].Units); + + // Find the order of each set. + RegUnitSetOrder.reserve(RegUnitSets.size()); + for (unsigned Idx = 0, EndIdx = RegUnitSets.size(); Idx != EndIdx; ++Idx) + RegUnitSetOrder.push_back(Idx); + + std::stable_sort(RegUnitSetOrder.begin(), RegUnitSetOrder.end(), + [this](unsigned ID1, unsigned ID2) { + return getRegPressureSet(ID1).Units.size() < + getRegPressureSet(ID2).Units.size(); + }); + for (unsigned Idx = 0, EndIdx = RegUnitSets.size(); Idx != EndIdx; ++Idx) { + RegUnitSets[RegUnitSetOrder[Idx]].Order = Idx; + } } // @@ -1802,7 +1923,7 @@ const CodeGenRegisterClass* CodeGenRegBank::getRegClassForRegister(Record *R) { const CodeGenRegister *Reg = getReg(R); ArrayRef RCs = getRegClasses(); - const CodeGenRegisterClass *FoundRC = 0; + const CodeGenRegisterClass *FoundRC = nullptr; for (unsigned i = 0, e = RCs.size(); i != e; ++i) { const CodeGenRegisterClass &RC = *RCs[i]; if (!RC.contains(Reg)) @@ -1817,7 +1938,7 @@ CodeGenRegBank::getRegClassForRegister(Record *R) { // If a register's classes have different types, return null. if (RC.getValueTypes() != FoundRC->getValueTypes()) - return 0; + return nullptr; // Check to see if the previously found class that contains // the register is a subclass of the current class. If so, @@ -1835,7 +1956,7 @@ CodeGenRegBank::getRegClassForRegister(Record *R) { // Multiple classes, and neither is a superclass of the other. // Return null. - return 0; + return nullptr; } return FoundRC; }