X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=utils%2FTableGen%2FCodeGenRegisters.cpp;h=f2eef4f68f5a7a18119e00329a0b32f64d04d1a0;hb=e778f82a1e33826ab012bb970a406c9acf37349b;hp=0db11d48eae284cc7e5924c4d0944e05666f1a61;hpb=4ffd89fa4d2788611187d1a534d2ed46adf1702c;p=oota-llvm.git diff --git a/utils/TableGen/CodeGenRegisters.cpp b/utils/TableGen/CodeGenRegisters.cpp index 0db11d48eae..f2eef4f68f5 100644 --- a/utils/TableGen/CodeGenRegisters.cpp +++ b/utils/TableGen/CodeGenRegisters.cpp @@ -12,6 +12,8 @@ // //===----------------------------------------------------------------------===// +#define DEBUG_TYPE "regalloc-emitter" + #include "CodeGenRegisters.h" #include "CodeGenTarget.h" #include "llvm/ADT/IntEqClasses.h" @@ -19,6 +21,7 @@ #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; @@ -28,15 +31,18 @@ using namespace llvm; //===----------------------------------------------------------------------===// CodeGenSubRegIndex::CodeGenSubRegIndex(Record *R, unsigned Enum) - : TheDef(R), EnumValue(Enum), LaneMask(0) { + : TheDef(R), EnumValue(Enum), LaneMask(0), AllSuperRegsCovered(true) { 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) { + : TheDef(0), Name(N), Namespace(Nspace), Size(-1), Offset(-1), + EnumValue(Enum), LaneMask(0), AllSuperRegsCovered(true) { } std::string CodeGenSubRegIndex::getQualifiedName() const { @@ -68,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])); @@ -312,6 +318,11 @@ CodeGenRegister::computeSubRegs(CodeGenRegBank &RegBank) { PrintFatalError(Loc, "Register " + getName() + " has itself as a sub-register"); } + + // Compute AllSuperRegsCovered. + if (!CoveredBySubRegs) + SI->first->AllSuperRegsCovered = false; + // Ensure that every sub-register has a unique name. DenseMap::iterator Ins = SubReg2Idx.insert(std::make_pair(SI->second, SI->first)).first; @@ -520,55 +531,6 @@ CodeGenRegister::addSubRegsPreOrder(SetVector &OSet, OSet.insert(I->second); } -// Compute 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 CodeGenRegister::computeOverlaps(CodeGenRegister::Set &Overlaps, - const CodeGenRegBank &RegBank) const { - assert(!RegUnits.empty() && "Compute register units before overlaps."); - - // Register units are assigned such that the overlapping registers are the - // super-registers of the root registers of the register units. - for (unsigned rui = 0, rue = RegUnits.size(); rui != rue; ++rui) { - const RegUnit &RU = RegBank.getRegUnit(RegUnits[rui]); - ArrayRef Roots = RU.getRoots(); - for (unsigned ri = 0, re = Roots.size(); ri != re; ++ri) { - const CodeGenRegister *Root = Roots[ri]; - Overlaps.insert(Root); - ArrayRef Supers = Root->getSuperRegs(); - Overlaps.insert(Supers.begin(), Supers.end()); - } - } -} - // Get the sum of this register's unit weights. unsigned CodeGenRegister::getWeight(const CodeGenRegBank &RegBank) const { unsigned Weight = 0; @@ -636,8 +598,10 @@ struct TupleExpander : SetTheory::Expander { Elts.insert(NewReg); // Copy Proto super-classes. - for (unsigned i = 0, e = Proto->getSuperClasses().size(); i != e; ++i) - NewReg->addSuperClass(Proto->getSuperClasses()[i]); + ArrayRef Supers = Proto->getSuperClasses(); + ArrayRef Ranges = Proto->getSuperClassRanges(); + for (unsigned i = 0, e = Supers.size(); i != e; ++i) + NewReg->addSuperClass(Supers[i], Ranges[i]); // Copy Proto fields. for (unsigned i = 0, e = Proto->getValues().size(); i != e; ++i) { @@ -701,7 +665,9 @@ CodeGenRegisterClass::CodeGenRegisterClass(CodeGenRegBank &RegBank, Record *R) // Rename anonymous register classes. if (R->getName().size() > 9 && R->getName()[9] == '.') { static unsigned AnonCounter = 0; - R->setName("AnonRegClass_"+utostr(AnonCounter++)); + R->setName("AnonRegClass_" + utostr(AnonCounter)); + // MSVC2012 ICEs if AnonCounter++ is directly passed to utostr. + ++AnonCounter; } std::vector TypeList = R->getValueAsListOfDefs("RegTypes"); @@ -847,9 +813,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; @@ -975,7 +942,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) @@ -984,10 +951,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 @@ -1119,7 +1092,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. @@ -1129,11 +1102,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() { @@ -1191,12 +1177,25 @@ void CodeGenRegBank::computeComposites() { void CodeGenRegBank::computeSubRegIndexLaneMasks() { // First assign individual bits to all the leaf indices. unsigned Bit = 0; + // Determine mask of lanes that cover their registers. + CoveringLanes = ~0u; for (unsigned i = 0, e = SubRegIndices.size(); i != e; ++i) { CodeGenSubRegIndex *Idx = SubRegIndices[i]; if (Idx->getComposites().empty()) { Idx->LaneMask = 1u << Bit; // Share bit 31 in the unlikely case there are more than 32 leafs. - if (Bit < 31) ++Bit; + // + // Sharing bits is harmless; it allows graceful degradation in targets + // with more than 32 vector lanes. They simply get a limited resolution + // view of lanes beyond the 32nd. + // + // See also the comment for getSubRegIndexLaneMask(). + if (Bit < 31) + ++Bit; + else + // Once bit 31 is shared among multiple leafs, the 'lane' it represents + // is no longer covering its registers. + CoveringLanes &= ~(1u << Bit); } else { Idx->LaneMask = 0; } @@ -1206,8 +1205,13 @@ void CodeGenRegBank::computeSubRegIndexLaneMasks() { // by the sub-register graph? This doesn't occur in any known targets. // Inherit lanes from composites. - for (unsigned i = 0, e = SubRegIndices.size(); i != e; ++i) - SubRegIndices[i]->computeLaneMask(); + for (unsigned i = 0, e = SubRegIndices.size(); i != e; ++i) { + unsigned Mask = SubRegIndices[i]->computeLaneMask(); + // If some super-registers without CoveredBySubRegs use this index, we can + // no longer assume that the lanes are covering their registers. + if (!SubRegIndices[i]->AllSuperRegsCovered) + CoveringLanes &= ~Mask; + } } namespace { @@ -1329,9 +1333,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(), @@ -1458,7 +1471,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"); @@ -1472,9 +1501,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; } } @@ -1499,6 +1533,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(); @@ -1521,9 +1556,32 @@ void CodeGenRegBank::computeRegUnitSets() { 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) { @@ -1561,12 +1619,31 @@ void CodeGenRegBank::computeRegUnitSets() { findRegUnitSet(RegUnitSets, RegUnitSets.back()); if (SetI != llvm::prior(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) { @@ -1574,23 +1651,70 @@ 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"); } + + // For each register unit, ensure that we have the list of UnitSets that + // contain the unit. Normally, this matches an existing list of UnitSets for a + // register class. If not, we create a new entry in RegClassUnitSets as a + // "fake" register class. + for (unsigned UnitIdx = 0, UnitEnd = NumNativeRegUnits; + UnitIdx < UnitEnd; ++UnitIdx) { + std::vector RUSets; + for (unsigned i = 0, e = RegUnitSets.size(); i != e; ++i) { + RegUnitSet &RUSet = RegUnitSets[i]; + if (std::find(RUSet.Units.begin(), RUSet.Units.end(), UnitIdx) + == RUSet.Units.end()) + continue; + RUSets.push_back(i); + } + unsigned RCUnitSetsIdx = 0; + for (unsigned e = RegClassUnitSets.size(); + RCUnitSetsIdx != e; ++RCUnitSetsIdx) { + if (RegClassUnitSets[RCUnitSetsIdx] == RUSets) { + break; + } + } + RegUnits[UnitIdx].RegClassUnitSetsIdx = RCUnitSetsIdx; + if (RCUnitSetsIdx == RegClassUnitSets.size()) { + // Create a new list of UnitSets as a "fake" register class. + RegClassUnitSets.resize(RCUnitSetsIdx + 1); + RegClassUnitSets[RCUnitSetsIdx].swap(RUSets); + } + } } +struct LessUnits { + const CodeGenRegBank &RegBank; + LessUnits(const CodeGenRegBank &RB): RegBank(RB) {} + + bool operator()(unsigned ID1, unsigned ID2) { + return RegBank.getRegPressureSet(ID1).Units.size() + < RegBank.getRegPressureSet(ID2).Units.size(); + } +}; + void CodeGenRegBank::computeDerivedInfo() { computeComposites(); computeSubRegIndexLaneMasks(); @@ -1602,6 +1726,21 @@ 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(), + LessUnits(*this)); + for (unsigned Idx = 0, EndIdx = RegUnitSets.size(); Idx != EndIdx; ++Idx) { + RegUnitSets[RegUnitSetOrder[Idx]].Order = Idx; + } } //