X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=utils%2FTableGen%2FCodeGenRegisters.cpp;h=f2eef4f68f5a7a18119e00329a0b32f64d04d1a0;hb=e778f82a1e33826ab012bb970a406c9acf37349b;hp=d9f230ef1c7bf0486893f1c69cb61775b3c21e4d;hpb=a0ec3f9b7b826b9b40b80199923b664bad808cce;p=oota-llvm.git diff --git a/utils/TableGen/CodeGenRegisters.cpp b/utils/TableGen/CodeGenRegisters.cpp index d9f230ef1c7..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; @@ -810,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; @@ -956,7 +960,7 @@ CodeGenRegBank::CodeGenRegBank(RecordKeeper &Records) { std::sort(TupRegsCopy.begin(), TupRegsCopy.end(), LessRecordRegister()); for (unsigned j = 0, je = TupRegsCopy.size(); j != je; ++j) getReg((TupRegsCopy)[j]); - TupRegsCopy.clear(); + TupRegsCopy.clear(); } // Now all the registers are known. Build the object graph of explicit @@ -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,19 +1651,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"); } @@ -1620,6 +1705,16 @@ void CodeGenRegBank::computeRegUnitSets() { } } +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(); @@ -1631,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; + } } //