X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=utils%2FTableGen%2FCodeGenRegisters.cpp;h=c9e6d1d379de95a50921b040337f71efec9e1230;hb=47f0e3f434e2e43f951c3a826c40906cb15b7285;hp=813a71ab3bda722138f46b5529be18d2412af8d4;hpb=3778aeb74864390bf763424c45cc355ac330fbc9;p=oota-llvm.git diff --git a/utils/TableGen/CodeGenRegisters.cpp b/utils/TableGen/CodeGenRegisters.cpp index 813a71ab3bd..c9e6d1d379d 100644 --- a/utils/TableGen/CodeGenRegisters.cpp +++ b/utils/TableGen/CodeGenRegisters.cpp @@ -14,33 +14,35 @@ #include "CodeGenRegisters.h" #include "CodeGenTarget.h" -#include "llvm/TableGen/Error.h" #include "llvm/ADT/IntEqClasses.h" -#include "llvm/ADT/SmallVector.h" #include "llvm/ADT/STLExtras.h" +#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 //===----------------------------------------------------------------------===// CodeGenSubRegIndex::CodeGenSubRegIndex(Record *R, unsigned Enum) - : TheDef(R), - EnumValue(Enum) -{} - -std::string CodeGenSubRegIndex::getNamespace() const { - if (TheDef->getValue("Namespace")) - return TheDef->getValueAsString("Namespace"); - else - return ""; + : 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"); } -const std::string &CodeGenSubRegIndex::getName() const { - return TheDef->getName(); +CodeGenSubRegIndex::CodeGenSubRegIndex(StringRef N, StringRef Nspace, + unsigned Enum) + : TheDef(nullptr), Name(N), Namespace(Nspace), Size(-1), Offset(-1), + EnumValue(Enum), LaneMask(0), AllSuperRegsCovered(true) { } std::string CodeGenSubRegIndex::getQualifiedName() const { @@ -52,28 +54,51 @@ std::string CodeGenSubRegIndex::getQualifiedName() const { } void CodeGenSubRegIndex::updateComponents(CodeGenRegBank &RegBank) { - std::vector Comps = TheDef->getValueAsListOfDefs("ComposedOf"); - if (Comps.empty()) + if (!TheDef) return; - if (Comps.size() != 2) - throw TGError(TheDef->getLoc(), "ComposedOf must have exactly two entries"); - CodeGenSubRegIndex *A = RegBank.getSubRegIdx(Comps[0]); - CodeGenSubRegIndex *B = RegBank.getSubRegIdx(Comps[1]); - CodeGenSubRegIndex *X = A->addComposite(B, this); - if (X) - throw TGError(TheDef->getLoc(), "Ambiguous ComposedOf entries"); -} -void CodeGenSubRegIndex::cleanComposites() { - // Clean out redundant mappings of the form this+X -> X. - for (CompMap::iterator i = Composed.begin(), e = Composed.end(); i != e;) { - CompMap::iterator j = i; - ++i; - if (j->first == j->second) - Composed.erase(j); + std::vector Comps = TheDef->getValueAsListOfDefs("ComposedOf"); + if (!Comps.empty()) { + if (Comps.size() != 2) + PrintFatalError(TheDef->getLoc(), + "ComposedOf must have exactly two entries"); + CodeGenSubRegIndex *A = RegBank.getSubRegIdx(Comps[0]); + CodeGenSubRegIndex *B = RegBank.getSubRegIdx(Comps[1]); + CodeGenSubRegIndex *X = A->addComposite(B, this); + if (X) + PrintFatalError(TheDef->getLoc(), "Ambiguous ComposedOf entries"); + } + + std::vector Parts = + TheDef->getValueAsListOfDefs("CoveringSubRegIndices"); + if (!Parts.empty()) { + if (Parts.size() < 2) + PrintFatalError(TheDef->getLoc(), + "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])); + RegBank.addConcatSubRegIndex(IdxParts, this); } } +unsigned CodeGenSubRegIndex::computeLaneMask() const { + // Already computed? + if (LaneMask) + return LaneMask; + + // Recursion guard, shouldn't be required. + LaneMask = ~0u; + + // The lane mask is simply the union of all sub-indices. + unsigned M = 0; + for (const auto &C : Composed) + M |= C.second->computeLaneMask(); + assert(M && "Missing lane mask, sub-register cycle?"); + LaneMask = M; + return LaneMask; +} + //===----------------------------------------------------------------------===// // CodeGenRegister //===----------------------------------------------------------------------===// @@ -83,6 +108,7 @@ CodeGenRegister::CodeGenRegister(Record *R, unsigned Enum) EnumValue(Enum), CostPerUse(R->getValueAsInt("CostPerUse")), CoveredBySubRegs(R->getValueAsBit("CoveredBySubRegs")), + HasDisjunctSubRegs(false), SubRegsComplete(false), SuperRegsComplete(false), TopoSig(~0u) @@ -93,8 +119,8 @@ void CodeGenRegister::buildObjectGraph(CodeGenRegBank &RegBank) { std::vector SRs = TheDef->getValueAsListOfDefs("SubRegs"); if (SRIs.size() != SRs.size()) - throw TGError(TheDef->getLoc(), - "SubRegs and SubRegIndices must have the same size"); + PrintFatalError(TheDef->getLoc(), + "SubRegs and SubRegIndices must have the same size"); for (unsigned i = 0, e = SRIs.size(); i != e; ++i) { ExplicitSubRegIndices.push_back(RegBank.getSubRegIdx(SRIs[i])); @@ -109,7 +135,7 @@ void CodeGenRegister::buildObjectGraph(CodeGenRegBank &RegBank) { if (CoveredBySubRegs && !ExplicitSubRegs.empty()) ExplicitSubRegs.front()->LeadingSuperRegs.push_back(this); - // Add ad hoc alias links. This is a symmetric relationship betwen two + // Add ad hoc alias links. This is a symmetric relationship between two // registers, so build a symmetric graph by adding links in both ends. std::vector Aliases = TheDef->getValueAsListOfDefs("Aliases"); for (unsigned i = 0, e = Aliases.size(); i != e; ++i) { @@ -120,17 +146,18 @@ void CodeGenRegister::buildObjectGraph(CodeGenRegBank &RegBank) { } const std::string &CodeGenRegister::getName() const { + assert(TheDef && "no def"); return TheDef->getName(); } namespace { // Iterate over all register units in a set of registers. class RegUnitIterator { - CodeGenRegister::Set::const_iterator RegI, RegE; - CodeGenRegister::RegUnitList::const_iterator UnitI, UnitE; + CodeGenRegister::Vec::const_iterator RegI, RegE; + CodeGenRegister::RegUnitList::iterator UnitI, UnitE; public: - RegUnitIterator(const CodeGenRegister::Set &Regs): + RegUnitIterator(const CodeGenRegister::Vec &Regs): RegI(Regs.begin()), RegE(Regs.end()), UnitI(), UnitE() { if (RegI != RegE) { @@ -165,35 +192,23 @@ protected: }; } // namespace -// Merge two RegUnitLists maintaining the order and removing duplicates. -// Overwrites MergedRU in the process. -static void mergeRegUnits(CodeGenRegister::RegUnitList &MergedRU, - const CodeGenRegister::RegUnitList &RRU) { - CodeGenRegister::RegUnitList LRU = MergedRU; - MergedRU.clear(); - std::set_union(LRU.begin(), LRU.end(), RRU.begin(), RRU.end(), - std::back_inserter(MergedRU)); -} - // Return true of this unit appears in RegUnits. static bool hasRegUnit(CodeGenRegister::RegUnitList &RegUnits, unsigned Unit) { - return std::count(RegUnits.begin(), RegUnits.end(), Unit); + return RegUnits.test(Unit); } // Inherit register units from subregisters. // Return true if the RegUnits changed. bool CodeGenRegister::inheritRegUnits(CodeGenRegBank &RegBank) { - unsigned OldNumUnits = RegUnits.size(); + bool changed = false; for (SubRegMap::const_iterator I = SubRegs.begin(), E = SubRegs.end(); I != E; ++I) { - // Strangely a register may have itself as a subreg (self-cycle) e.g. XMM. CodeGenRegister *SR = I->second; - if (SR == this) - continue; // Merge the subregister's units into this register's RegUnits. - mergeRegUnits(RegUnits, SR->RegUnits); + changed |= (RegUnits |= SR->RegUnits); } - return OldNumUnits != RegUnits.size(); + + return changed; } const CodeGenRegister::SubRegMap & @@ -203,13 +218,15 @@ CodeGenRegister::computeSubRegs(CodeGenRegBank &RegBank) { return SubRegs; SubRegsComplete = true; + HasDisjunctSubRegs = ExplicitSubRegs.size() > 1; + // First insert the explicit subregs and make sure they are fully indexed. for (unsigned i = 0, e = ExplicitSubRegs.size(); i != e; ++i) { CodeGenRegister *SR = ExplicitSubRegs[i]; CodeGenSubRegIndex *Idx = ExplicitSubRegIndices[i]; if (!SubRegs.insert(std::make_pair(Idx, SR)).second) - throw TGError(TheDef->getLoc(), "SubRegIndex " + Idx->getName() + - " appears twice in Register " + getName()); + PrintFatalError(TheDef->getLoc(), "SubRegIndex " + Idx->getName() + + " appears twice in Register " + getName()); // Map explicit sub-registers first, so the names take precedence. // The inherited sub-registers are mapped below. SubReg2Idx.insert(std::make_pair(SR, Idx)); @@ -223,6 +240,7 @@ CodeGenRegister::computeSubRegs(CodeGenRegBank &RegBank) { for (unsigned i = 0, e = ExplicitSubRegs.size(); i != e; ++i) { CodeGenRegister *SR = ExplicitSubRegs[i]; const SubRegMap &Map = SR->computeSubRegs(RegBank); + HasDisjunctSubRegs |= SR->HasDisjunctSubRegs; for (SubRegMap::const_iterator SI = Map.begin(), SE = Map.end(); SI != SE; ++SI) { @@ -259,44 +277,6 @@ CodeGenRegister::computeSubRegs(CodeGenRegBank &RegBank) { } } - // Process the composites. - ListInit *Comps = TheDef->getValueAsListInit("CompositeIndices"); - for (unsigned i = 0, e = Comps->size(); i != e; ++i) { - DagInit *Pat = dynamic_cast(Comps->getElement(i)); - if (!Pat) - throw TGError(TheDef->getLoc(), "Invalid dag '" + - Comps->getElement(i)->getAsString() + - "' in CompositeIndices"); - DefInit *BaseIdxInit = dynamic_cast(Pat->getOperator()); - if (!BaseIdxInit || !BaseIdxInit->getDef()->isSubClassOf("SubRegIndex")) - throw TGError(TheDef->getLoc(), "Invalid SubClassIndex in " + - Pat->getAsString()); - CodeGenSubRegIndex *BaseIdx = RegBank.getSubRegIdx(BaseIdxInit->getDef()); - - // Resolve list of subreg indices into R2. - CodeGenRegister *R2 = this; - for (DagInit::const_arg_iterator di = Pat->arg_begin(), - de = Pat->arg_end(); di != de; ++di) { - DefInit *IdxInit = dynamic_cast(*di); - if (!IdxInit || !IdxInit->getDef()->isSubClassOf("SubRegIndex")) - throw TGError(TheDef->getLoc(), "Invalid SubClassIndex in " + - Pat->getAsString()); - CodeGenSubRegIndex *Idx = RegBank.getSubRegIdx(IdxInit->getDef()); - const SubRegMap &R2Subs = R2->computeSubRegs(RegBank); - SubRegMap::const_iterator ni = R2Subs.find(Idx); - if (ni == R2Subs.end()) - throw TGError(TheDef->getLoc(), "Composite " + Pat->getAsString() + - " refers to bad index in " + R2->getName()); - R2 = ni->second; - } - - // Insert composite index. Allow overriding inherited indices etc. - SubRegs[BaseIdx] = R2; - - // R2 is no longer an orphan. - Orphans.erase(R2); - } - // Now Orphans contains the inherited subregisters without a direct index. // Create inferred indexes for all missing entries. // Work backwards in the Indices vector in order to compose subregs bottom-up. @@ -311,7 +291,7 @@ CodeGenRegister::computeSubRegs(CodeGenRegBank &RegBank) { // dsub_2 -> ssub_0 // // We pick the latter composition because another register may have [dsub_0, - // dsub_1, dsub_2] subregs without neccessarily having a qsub_1 subreg. The + // dsub_1, dsub_2] subregs without necessarily having a qsub_1 subreg. The // dsub_2 -> ssub_0 composition can be shared. while (!Indices.empty() && !Orphans.empty()) { CodeGenSubRegIndex *Idx = Indices.pop_back_val(); @@ -326,14 +306,30 @@ CodeGenRegister::computeSubRegs(CodeGenRegBank &RegBank) { // Compute the inverse SubReg -> Idx map. for (SubRegMap::const_iterator SI = SubRegs.begin(), SE = SubRegs.end(); SI != SE; ++SI) { - // Ignore idempotent sub-register indices. - if (SI->second == this) + if (SI->second == this) { + ArrayRef Loc; + if (TheDef) + Loc = TheDef->getLoc(); + 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; + if (Ins->second == SI->first) continue; - // Is is possible to have multiple names for the same sub-register. - // For example, XMM0 appears as sub_xmm, sub_sd, and sub_ss in YMM0. - // Eventually, this degeneration should go away, but for now we simply give - // precedence to the explicit sub-register index over the inherited ones. - SubReg2Idx.insert(std::make_pair(SI->second, SI->first)); + // Trouble: Two different names for SI->second. + ArrayRef Loc; + if (TheDef) + Loc = TheDef->getLoc(); + PrintFatalError(Loc, "Sub-register can't have two names: " + + SI->second->getName() + " available as " + + SI->first->getName() + " and " + Ins->second->getName()); } // Derive possible names for sub-register concatenations from any explicit @@ -361,14 +357,8 @@ CodeGenRegister::computeSubRegs(CodeGenRegBank &RegBank) { // sub-registers, the other registers won't contribute any more units. for (unsigned i = 0, e = ExplicitSubRegs.size(); i != e; ++i) { CodeGenRegister *SR = ExplicitSubRegs[i]; - // Explicit sub-registers are usually disjoint, so this is a good way of - // computing the union. We may pick up a few duplicates that will be - // eliminated below. - unsigned N = RegUnits.size(); - RegUnits.append(SR->RegUnits.begin(), SR->RegUnits.end()); - std::inplace_merge(RegUnits.begin(), RegUnits.begin() + N, RegUnits.end()); + RegUnits |= SR->RegUnits; } - RegUnits.erase(std::unique(RegUnits.begin(), RegUnits.end()), RegUnits.end()); // Absent any ad hoc aliasing, we create one register unit per leaf register. // These units correspond to the maximal cliques in the register overlap @@ -387,15 +377,19 @@ CodeGenRegister::computeSubRegs(CodeGenRegBank &RegBank) { // Create a RegUnit representing this alias edge, and add it to both // registers. unsigned Unit = RegBank.newRegUnit(this, AR); - RegUnits.push_back(Unit); - AR->RegUnits.push_back(Unit); + RegUnits.set(Unit); + AR->RegUnits.set(Unit); } // Finally, create units for leaf registers without ad hoc aliases. Note that // a leaf register with ad hoc aliases doesn't get its own unit - it isn't // necessary. This means the aliasing leaf registers can share a single unit. if (RegUnits.empty()) - RegUnits.push_back(RegBank.newRegUnit(this)); + RegUnits.set(RegBank.newRegUnit(this)); + + // We have now computed the native register units. More may be adopted later + // for balancing purposes. + NativeRegUnits = RegUnits; return SubRegs; } @@ -474,8 +468,8 @@ void CodeGenRegister::computeSecondarySubRegs(CodeGenRegBank &RegBank) { SE = NewSubReg->SubRegs.end(); SI != SE; ++SI) { CodeGenSubRegIndex *SubIdx = getSubRegIndex(SI->second); if (!SubIdx) - throw TGError(TheDef->getLoc(), "No SubRegIndex for " + - SI->second->getName() + " in " + getName()); + PrintFatalError(TheDef->getLoc(), "No SubRegIndex for " + + SI->second->getName() + " in " + getName()); NewIdx->addComposite(SI->first, SubIdx); } } @@ -503,8 +497,6 @@ void CodeGenRegister::computeSuperRegs(CodeGenRegBank &RegBank) { Id.push_back(I->first->EnumValue); Id.push_back(I->second->TopoSig); - if (I->second == this) - continue; // Don't add duplicate entries. if (!I->second->SuperRegs.empty() && I->second->SuperRegs.back() == this) continue; @@ -525,63 +517,13 @@ CodeGenRegister::addSubRegsPreOrder(SetVector &OSet, // Add any secondary sub-registers that weren't part of the explicit tree. for (SubRegMap::const_iterator I = SubRegs.begin(), E = SubRegs.end(); I != E; ++I) - if (I->second != this) - 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()); - } - } + OSet.insert(I->second); } // Get the sum of this register's unit weights. unsigned CodeGenRegister::getWeight(const CodeGenRegBank &RegBank) const { unsigned Weight = 0; - for (RegUnitList::const_iterator I = RegUnits.begin(), E = RegUnits.end(); + for (RegUnitList::iterator I = RegUnits.begin(), E = RegUnits.end(); I != E; ++I) { Weight += RegBank.getRegUnit(*I).Weight; } @@ -597,20 +539,21 @@ 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"); - if (Dim != SubRegs->getSize()) - throw TGError(Def->getLoc(), "SubRegIndices and SubRegs size mismatch"); + if (Dim != SubRegs->size()) + PrintFatalError(Def->getLoc(), "SubRegIndices and SubRegs size mismatch"); if (Dim < 2) - throw TGError(Def->getLoc(), "Tuples must have at least 2 sub-registers"); + PrintFatalError(Def->getLoc(), + "Tuples must have at least 2 sub-registers"); // Evaluate the sub-register lists to be zipped. unsigned Length = ~0u; SmallVector Lists(Dim); for (unsigned i = 0; i != Dim; ++i) { - ST.evaluate(SubRegs->getElement(i), Lists[i]); + ST.evaluate(SubRegs->getElement(i), Lists[i], Def->getLoc()); Length = std::min(Length, unsigned(Lists[i].size())); } @@ -644,8 +587,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,23 +646,29 @@ struct TupleExpander : SetTheory::Expander { // CodeGenRegisterClass //===----------------------------------------------------------------------===// +static void sortAndUniqueRegisters(CodeGenRegister::Vec &M) { + std::sort(M.begin(), M.end(), deref()); + M.erase(std::unique(M.begin(), M.end(), deref()), M.end()); +} + CodeGenRegisterClass::CodeGenRegisterClass(CodeGenRegBank &RegBank, Record *R) : TheDef(R), Name(R->getName()), TopoSigs(RegBank.getNumTopoSigs()), - EnumValue(-1) { + EnumValue(-1), + LaneMask(0) { // 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++)); } std::vector TypeList = R->getValueAsListOfDefs("RegTypes"); for (unsigned i = 0, e = TypeList.size(); i != e; ++i) { Record *Type = TypeList[i]; if (!Type->isSubClassOf("ValueType")) - throw "RegTypes list member '" + Type->getName() + - "' does not derive from the ValueType class!"; + PrintFatalError("RegTypes list member '" + Type->getName() + + "' does not derive from the ValueType class!"); VTs.push_back(getValueType(Type)); } assert(!VTs.empty() && "RegisterClass must contain at least one ValueType!"); @@ -731,21 +682,22 @@ CodeGenRegisterClass::CodeGenRegisterClass(CodeGenRegBank &RegBank, Record *R) for (unsigned i = 0, e = Elements->size(); i != e; ++i) { Orders[0].push_back((*Elements)[i]); const CodeGenRegister *Reg = RegBank.getReg((*Elements)[i]); - Members.insert(Reg); + Members.push_back(Reg); TopoSigs.set(Reg->getTopoSig()); } + sortAndUniqueRegisters(Members); // Alternative allocation orders may be subsets. SetTheory::RecSet Order; for (unsigned i = 0, e = AltOrders->size(); i != e; ++i) { - RegBank.getSets().evaluate(AltOrders->getElement(i), Order); + RegBank.getSets().evaluate(AltOrders->getElement(i), Order, R->getLoc()); Orders[1 + 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() + + PrintFatalError(R->getLoc(), " AltOrder register " + Reg->getName() + " is not a class member"); } } @@ -754,25 +706,34 @@ 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"); AltOrderSelect = R->getValueAsString("AltOrderSelect"); + int AllocationPriority = R->getValueAsInt("AllocationPriority"); + if (AllocationPriority < 0 || AllocationPriority > 63) + PrintFatalError(R->getLoc(), "AllocationPriority out of range [0,63]"); + this->AllocationPriority = AllocationPriority; } // Create an inferred register class that was missing from the .td files. // Most properties will be inherited from the closest super-class after the // class structure has been computed. -CodeGenRegisterClass::CodeGenRegisterClass(StringRef Name, Key Props) +CodeGenRegisterClass::CodeGenRegisterClass(CodeGenRegBank &RegBank, + StringRef Name, Key Props) : Members(*Props.Members), - TheDef(0), + TheDef(nullptr), Name(Name), + TopoSigs(RegBank.getNumTopoSigs()), EnumValue(-1), SpillSize(Props.SpillSize), SpillAlignment(Props.SpillAlignment), CopyCost(0), - Allocatable(true) { + Allocatable(true), + AllocationPriority(0) { + for (const auto R : Members) + TopoSigs.set(R->getTopoSig()); } // Compute inherited propertied for a synthesized register class. @@ -790,6 +751,7 @@ void CodeGenRegisterClass::inheritProperties(CodeGenRegBank &RegBank) { CopyCost = Super.CopyCost; Allocatable = Super.Allocatable; AltOrderSelect = Super.AltOrderSelect; + AllocationPriority = Super.AllocationPriority; // Copy all allocation orders, filter out foreign registers from the larger // super-class. @@ -801,15 +763,15 @@ void CodeGenRegisterClass::inheritProperties(CodeGenRegBank &RegBank) { } bool CodeGenRegisterClass::contains(const CodeGenRegister *Reg) const { - return Members.count(Reg); + return std::binary_search(Members.begin(), Members.end(), Reg, + deref()); } namespace llvm { raw_ostream &operator<<(raw_ostream &OS, const CodeGenRegisterClass::Key &K) { OS << "{ S=" << K.SpillSize << ", A=" << K.SpillAlignment; - for (CodeGenRegister::Set::const_iterator I = K.Members->begin(), - E = K.Members->end(); I != E; ++I) - OS << ", " << (*I)->getName(); + for (const auto R : *K.Members) + OS << ", " << R->getName(); return OS << " }"; } } @@ -819,11 +781,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. @@ -838,10 +797,10 @@ operator<(const CodeGenRegisterClass::Key &B) const { static bool testSubClass(const CodeGenRegisterClass *A, const CodeGenRegisterClass *B) { return A->SpillAlignment && B->SpillAlignment % A->SpillAlignment == 0 && - A->SpillSize <= B->SpillSize && - std::includes(A->getMembers().begin(), A->getMembers().end(), - B->getMembers().begin(), B->getMembers().end(), - CodeGenRegister::Less()); + A->SpillSize <= B->SpillSize && + std::includes(A->getMembers().begin(), A->getMembers().end(), + B->getMembers().begin(), B->getMembers().end(), + deref()); } /// Sorting predicate for register classes. This provides a topological @@ -850,33 +809,34 @@ 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 bool TopoOrderRC(const CodeGenRegisterClass &PA, + const CodeGenRegisterClass &PB) { + auto *A = &PA; + auto *B = &PB; if (A == B) return 0; // Order by ascending spill size. if (A->SpillSize < B->SpillSize) - return -1; + return true; if (A->SpillSize > B->SpillSize) - return 1; + return false; // Order by ascending spill alignment. if (A->SpillAlignment < B->SpillAlignment) - return -1; + return true; if (A->SpillAlignment > B->SpillAlignment) - return 1; + return false; // Order by descending set size. Note that the classes' allocation order may // not have been computed yet. The Members set is always vaild. if (A->getMembers().size() > B->getMembers().size()) - return -1; + return true; if (A->getMembers().size() < B->getMembers().size()) - return 1; + return false; // Finally order by name as a tie breaker. - return StringRef(A->getName()).compare(B->getName()); + return StringRef(A->getName()) < B->getName(); } std::string CodeGenRegisterClass::getQualifiedName() const { @@ -889,60 +849,60 @@ std::string CodeGenRegisterClass::getQualifiedName() const { // Compute sub-classes of all register classes. // Assume the classes are ordered topologically. void CodeGenRegisterClass::computeSubClasses(CodeGenRegBank &RegBank) { - ArrayRef RegClasses = RegBank.getRegClasses(); + auto &RegClasses = RegBank.getRegClasses(); // Visit backwards so sub-classes are seen first. - for (unsigned rci = RegClasses.size(); rci; --rci) { - CodeGenRegisterClass &RC = *RegClasses[rci - 1]; + for (auto I = RegClasses.rbegin(), E = RegClasses.rend(); I != E; ++I) { + CodeGenRegisterClass &RC = *I; RC.SubClasses.resize(RegClasses.size()); RC.SubClasses.set(RC.EnumValue); // Normally, all subclasses have IDs >= rci, unless RC is part of a clique. - for (unsigned s = rci; s != RegClasses.size(); ++s) { - if (RC.SubClasses.test(s)) + for (auto I2 = I.base(), E2 = RegClasses.end(); I2 != E2; ++I2) { + CodeGenRegisterClass &SubRC = *I2; + if (RC.SubClasses.test(SubRC.EnumValue)) continue; - CodeGenRegisterClass *SubRC = RegClasses[s]; - if (!testSubClass(&RC, SubRC)) + if (!testSubClass(&RC, &SubRC)) continue; // SubRC is a sub-class. Grap all its sub-classes so we won't have to // check them again. - RC.SubClasses |= SubRC->SubClasses; + RC.SubClasses |= SubRC.SubClasses; } - // Sweep up missed clique members. They will be immediately preceeding RC. - for (unsigned s = rci - 1; s && testSubClass(&RC, RegClasses[s - 1]); --s) - RC.SubClasses.set(s - 1); + // Sweep up missed clique members. They will be immediately preceding RC. + for (auto I2 = std::next(I); I2 != E && testSubClass(&RC, &*I2); ++I2) + RC.SubClasses.set(I2->EnumValue); } // Compute the SuperClasses lists from the SubClasses vectors. - for (unsigned rci = 0; rci != RegClasses.size(); ++rci) { - const BitVector &SC = RegClasses[rci]->getSubClasses(); - for (int s = SC.find_first(); s >= 0; s = SC.find_next(s)) { - if (unsigned(s) == rci) + for (auto &RC : RegClasses) { + const BitVector &SC = RC.getSubClasses(); + auto I = RegClasses.begin(); + for (int s = 0, next_s = SC.find_first(); next_s != -1; + next_s = SC.find_next(s)) { + std::advance(I, next_s - s); + s = next_s; + if (&*I == &RC) continue; - RegClasses[s]->SuperClasses.push_back(RegClasses[rci]); + I->SuperClasses.push_back(&RC); } } // With the class hierarchy in place, let synthesized register classes inherit // properties from their closest super-class. The iteration order here can // propagate properties down multiple levels. - for (unsigned rci = 0; rci != RegClasses.size(); ++rci) - if (!RegClasses[rci]->getDef()) - RegClasses[rci]->inheritProperties(RegBank); + for (auto &RC : RegClasses) + if (!RC.getDef()) + RC.inheritProperties(RegBank); } -void -CodeGenRegisterClass::getSuperRegClasses(CodeGenSubRegIndex *SubIdx, - BitVector &Out) const { - DenseMap >::const_iterator - FindI = SuperRegClasses.find(SubIdx); +void CodeGenRegisterClass::getSuperRegClasses(const CodeGenSubRegIndex *SubIdx, + BitVector &Out) const { + auto FindI = SuperRegClasses.find(SubIdx); if (FindI == SuperRegClasses.end()) return; - for (SmallPtrSet::const_iterator I = - FindI->second.begin(), E = FindI->second.end(); I != E; ++I) - Out.set((*I)->EnumValue); + for (CodeGenRegisterClass *RC : FindI->second) + Out.set(RC->EnumValue); } // Populate a unique sorted list of units from a register set. @@ -960,27 +920,25 @@ void CodeGenRegisterClass::buildRegUnitSet( // CodeGenRegBank //===----------------------------------------------------------------------===// -CodeGenRegBank::CodeGenRegBank(RecordKeeper &Records) : Records(Records) { +CodeGenRegBank::CodeGenRegBank(RecordKeeper &Records) { // Configure register Sets to understand register classes and tuples. Sets.addFieldExpander("RegisterClass", "MemberList"); Sets.addFieldExpander("CalleeSavedRegs", "SaveList"); - Sets.addExpander("RegisterTuples", new TupleExpander()); + Sets.addExpander("RegisterTuples", llvm::make_unique()); // Read in the user-defined (named) sub-register indices. // More indices will be synthesized later. std::vector SRIs = Records.getAllDerivedDefinitions("SubRegIndex"); std::sort(SRIs.begin(), SRIs.end(), LessRecord()); - NumNamedIndices = SRIs.size(); for (unsigned i = 0, e = SRIs.size(); i != e; ++i) getSubRegIdx(SRIs[i]); // Build composite maps from ComposedOf fields. - for (unsigned i = 0, e = SubRegIndices.size(); i != e; ++i) - SubRegIndices[i]->updateComponents(*this); + for (auto &Idx : SubRegIndices) + Idx.updateComponents(*this); // Read in the register definitions. std::vector Regs = Records.getAllDerivedDefinitions("Register"); - std::sort(Regs.begin(), Regs.end(), LessRecord()); - Registers.reserve(Regs.size()); + std::sort(Regs.begin(), Regs.end(), LessRecordRegister()); // Assign the enumeration values. for (unsigned i = 0, e = Regs.size(); i != e; ++i) getReg(Regs[i]); @@ -988,31 +946,42 @@ CodeGenRegBank::CodeGenRegBank(RecordKeeper &Records) : Records(Records) { // Expand tuples and number the new registers. std::vector Tups = Records.getAllDerivedDefinitions("RegisterTuples"); - 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]); + + for (Record *R : Tups) { + std::vector TupRegs = *Sets.expand(R); + std::sort(TupRegs.begin(), TupRegs.end(), LessRecordRegister()); + for (Record *RC : TupRegs) + getReg(RC); } // Now all the registers are known. Build the object graph of explicit // register-register references. - for (unsigned i = 0, e = Registers.size(); i != e; ++i) - Registers[i]->buildObjectGraph(*this); + for (auto &Reg : Registers) + Reg.buildObjectGraph(*this); + + // Compute register name map. + for (auto &Reg : Registers) + // FIXME: This could just be RegistersByName[name] = register, except that + // causes some failures in MIPS - perhaps they have duplicate register name + // entries? (or maybe there's a reason for it - I don't know much about this + // code, just drive-by refactoring) + RegistersByName.insert( + std::make_pair(Reg.TheDef->getValueAsString("AsmName"), &Reg)); // 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]->computeSubRegs(*this); + for (auto &Reg : Registers) + Reg.computeSubRegs(*this); // Infer even more sub-registers by combining leading super-registers. - for (unsigned i = 0, e = Registers.size(); i != e; ++i) - if (Registers[i]->CoveredBySubRegs) - Registers[i]->computeSecondarySubRegs(*this); + for (auto &Reg : Registers) + if (Reg.CoveredBySubRegs) + Reg.computeSecondarySubRegs(*this); // After the sub-register graph is complete, compute the topologically // ordered SuperRegs list. - for (unsigned i = 0, e = Registers.size(); i != e; ++i) - Registers[i]->computeSuperRegs(*this); + for (auto &Reg : Registers) + Reg.computeSuperRegs(*this); // Native register units are associated with a leaf register. They've all been // discovered now. @@ -1021,29 +990,38 @@ CodeGenRegBank::CodeGenRegBank(RecordKeeper &Records) : Records(Records) { // Read in register class definitions. std::vector RCs = Records.getAllDerivedDefinitions("RegisterClass"); if (RCs.empty()) - throw std::string("No 'RegisterClass' subclasses defined!"); + PrintFatalError("No 'RegisterClass' subclasses defined!"); // Allocate user-defined register classes. - RegClasses.reserve(RCs.size()); - for (unsigned i = 0, e = RCs.size(); i != e; ++i) - addToMaps(new CodeGenRegisterClass(*this, RCs[i])); + for (auto *RC : RCs) { + RegClasses.emplace_back(*this, RC); + addToMaps(&RegClasses.back()); + } // Infer missing classes to create a full algebra. computeInferredRegisterClasses(); // Order register classes topologically and assign enum values. - array_pod_sort(RegClasses.begin(), RegClasses.end(), TopoOrderRC); - for (unsigned i = 0, e = RegClasses.size(); i != e; ++i) - RegClasses[i]->EnumValue = i; + RegClasses.sort(TopoOrderRC); + unsigned i = 0; + for (auto &RC : RegClasses) + RC.EnumValue = i++; CodeGenRegisterClass::computeSubClasses(*this); } +// Create a synthetic CodeGenSubRegIndex without a corresponding Record. +CodeGenSubRegIndex* +CodeGenRegBank::createSubRegIndex(StringRef Name, StringRef Namespace) { + SubRegIndices.emplace_back(Name, Namespace, SubRegIndices.size() + 1); + return &SubRegIndices.back(); +} + CodeGenSubRegIndex *CodeGenRegBank::getSubRegIdx(Record *Def) { CodeGenSubRegIndex *&Idx = Def2SubRegIdx[Def]; if (Idx) return Idx; - Idx = new CodeGenSubRegIndex(Def, SubRegIndices.size() + 1); - SubRegIndices.push_back(Idx); + SubRegIndices.emplace_back(Def, SubRegIndices.size() + 1); + Idx = &SubRegIndices.back(); return Idx; } @@ -1051,14 +1029,12 @@ CodeGenRegister *CodeGenRegBank::getReg(Record *Def) { CodeGenRegister *&Reg = Def2Reg[Def]; if (Reg) return Reg; - Reg = new CodeGenRegister(Def, Registers.size() + 1); - Registers.push_back(Reg); + Registers.emplace_back(Def, Registers.size() + 1); + Reg = &Registers.back(); return Reg; } void CodeGenRegBank::addToMaps(CodeGenRegisterClass *RC) { - RegClasses.push_back(RC); - if (Record *Def = RC->getDef()) Def2RC.insert(std::make_pair(Def, RC)); @@ -1071,7 +1047,7 @@ void CodeGenRegBank::addToMaps(CodeGenRegisterClass *RC) { // Create a synthetic sub-class if it is missing. CodeGenRegisterClass* CodeGenRegBank::getOrCreateSubClass(const CodeGenRegisterClass *RC, - const CodeGenRegister::Set *Members, + const CodeGenRegister::Vec *Members, StringRef Name) { // Synthetic sub-class has the same size and alignment as RC. CodeGenRegisterClass::Key K(Members, RC->SpillSize, RC->SpillAlignment); @@ -1080,16 +1056,16 @@ CodeGenRegBank::getOrCreateSubClass(const CodeGenRegisterClass *RC, return FoundI->second; // Sub-class doesn't exist, create a new one. - CodeGenRegisterClass *NewRC = new CodeGenRegisterClass(Name, K); - addToMaps(NewRC); - return NewRC; + RegClasses.emplace_back(*this, Name, K); + addToMaps(&RegClasses.back()); + return &RegClasses.back(); } CodeGenRegisterClass *CodeGenRegBank::getRegClass(Record *Def) { if (CodeGenRegisterClass *RC = Def2RC[Def]) return RC; - throw TGError(Def->getLoc(), "Not a known RegisterClass!"); + PrintFatalError(Def->getLoc(), "Not a known RegisterClass!"); } CodeGenSubRegIndex* @@ -1102,13 +1078,13 @@ CodeGenRegBank::getCompositeSubRegIndex(CodeGenSubRegIndex *A, // None exists, synthesize one. std::string Name = A->getName() + "_then_" + B->getName(); - Comp = getSubRegIdx(new Record(Name, SMLoc(), Records)); + Comp = createSubRegIndex(Name, A->getNamespace()); A->addComposite(B, Comp); return Comp; } CodeGenSubRegIndex *CodeGenRegBank:: -getConcatSubRegIndex(const SmallVector &Parts) { +getConcatSubRegIndex(const SmallVector &Parts) { assert(Parts.size() > 1 && "Need two parts to concatenate"); // Look for an existing entry. @@ -1118,11 +1094,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 = getSubRegIdx(new Record(Name, SMLoc(), Records)); + Idx = createSubRegIndex(Name, Parts.front()->getNamespace()); + Idx->Size = Size; + Idx->Offset = isContinuous ? Parts.front()->Offset : -1; + return Idx; } void CodeGenRegBank::computeComposites() { @@ -1130,21 +1119,19 @@ void CodeGenRegBank::computeComposites() { // and many registers will share TopoSigs on regular architectures. BitVector TopoSigs(getNumTopoSigs()); - for (unsigned i = 0, e = Registers.size(); i != e; ++i) { - CodeGenRegister *Reg1 = Registers[i]; - + for (const auto &Reg1 : Registers) { // Skip identical subreg structures already processed. - if (TopoSigs.test(Reg1->getTopoSig())) + if (TopoSigs.test(Reg1.getTopoSig())) continue; - TopoSigs.set(Reg1->getTopoSig()); + TopoSigs.set(Reg1.getTopoSig()); - const CodeGenRegister::SubRegMap &SRM1 = Reg1->getSubRegs(); + const CodeGenRegister::SubRegMap &SRM1 = Reg1.getSubRegs(); for (CodeGenRegister::SubRegMap::const_iterator i1 = SRM1.begin(), e1 = SRM1.end(); i1 != e1; ++i1) { CodeGenSubRegIndex *Idx1 = i1->first; CodeGenRegister *Reg2 = i1->second; // Ignore identity compositions. - if (Reg1 == Reg2) + if (&Reg1 == Reg2) continue; const CodeGenRegister::SubRegMap &SRM2 = Reg2->getSubRegs(); // Try composing Idx1 with another SubRegIndex. @@ -1156,7 +1143,7 @@ void CodeGenRegBank::computeComposites() { if (Reg2 == Reg3) continue; // OK Reg1:IdxPair == Reg3. Find the index with Reg:Idx == Reg3. - CodeGenSubRegIndex *Idx3 = Reg1->getSubRegIndex(Reg3); + CodeGenSubRegIndex *Idx3 = Reg1.getSubRegIndex(Reg3); assert(Idx3 && "Sub-register doesn't have an index"); // Conflicting composition? Emit a warning but allow it. @@ -1168,11 +1155,127 @@ void CodeGenRegBank::computeComposites() { } } } +} + +// Compute lane masks. This is similar to register units, but at the +// sub-register index level. Each bit in the lane mask is like a register unit +// class, and two lane masks will have a bit in common if two sub-register +// indices overlap in some register. +// +// Conservatively share a lane mask bit if two sub-register indices overlap in +// some registers, but not in others. That shouldn't happen a lot. +void CodeGenRegBank::computeSubRegLaneMasks() { + // First assign individual bits to all the leaf indices. + unsigned Bit = 0; + // Determine mask of lanes that cover their registers. + CoveringLanes = ~0u; + for (auto &Idx : SubRegIndices) { + if (Idx.getComposites().empty()) { + Idx.LaneMask = 1u << Bit; + // Share bit 31 in the unlikely case there are more than 32 leafs. + // + // 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; + } + } + + // Compute transformation sequences for composeSubRegIndexLaneMask. The idea + // here is that for each possible target subregister we look at the leafs + // in the subregister graph that compose for this target and create + // transformation sequences for the lanemasks. Each step in the sequence + // consists of a bitmask and a bitrotate operation. As the rotation amounts + // are usually the same for many subregisters we can easily combine the steps + // by combining the masks. + for (const auto &Idx : SubRegIndices) { + const auto &Composites = Idx.getComposites(); + auto &LaneTransforms = Idx.CompositionLaneMaskTransform; + // Go through all leaf subregisters and find the ones that compose with Idx. + // These make out all possible valid bits in the lane mask we want to + // transform. Looking only at the leafs ensure that only a single bit in + // the mask is set. + unsigned NextBit = 0; + for (auto &Idx2 : SubRegIndices) { + // Skip non-leaf subregisters. + if (!Idx2.getComposites().empty()) + continue; + // Replicate the behaviour from the lane mask generation loop above. + unsigned SrcBit = NextBit; + unsigned SrcMask = 1u << SrcBit; + if (NextBit < 31) + ++NextBit; + assert(Idx2.LaneMask == SrcMask); + + // Get the composed subregister if there is any. + auto C = Composites.find(&Idx2); + if (C == Composites.end()) + continue; + const CodeGenSubRegIndex *Composite = C->second; + // The Composed subreg should be a leaf subreg too + assert(Composite->getComposites().empty()); + + // Create Mask+Rotate operation and merge with existing ops if possible. + unsigned DstBit = Log2_32(Composite->LaneMask); + int Shift = DstBit - SrcBit; + uint8_t RotateLeft = Shift >= 0 ? (uint8_t)Shift : 32+Shift; + for (auto &I : LaneTransforms) { + if (I.RotateLeft == RotateLeft) { + I.Mask |= SrcMask; + SrcMask = 0; + } + } + if (SrcMask != 0) { + MaskRolPair MaskRol = { SrcMask, RotateLeft }; + LaneTransforms.push_back(MaskRol); + } + } + // Optimize if the transformation consists of one step only: Set mask to + // 0xffffffff (including some irrelevant invalid bits) so that it should + // merge with more entries later while compressing the table. + if (LaneTransforms.size() == 1) + LaneTransforms[0].Mask = ~0u; + + // Further compression optimization: For invalid compositions resulting + // in a sequence with 0 entries we can just pick any other. Choose + // Mask 0xffffffff with Rotation 0. + if (LaneTransforms.size() == 0) { + MaskRolPair P = { ~0u, 0 }; + LaneTransforms.push_back(P); + } + } - // We don't care about the difference between (Idx1, Idx2) -> Idx2 and invalid - // compositions, so remove any mappings of that form. - for (unsigned i = 0, e = SubRegIndices.size(); i != e; ++i) - SubRegIndices[i]->cleanComposites(); + // FIXME: What if ad-hoc aliasing introduces overlaps that aren't represented + // by the sub-register graph? This doesn't occur in any known targets. + + // Inherit lanes from composites. + for (const auto &Idx : SubRegIndices) { + unsigned Mask = Idx.computeLaneMask(); + // If some super-registers without CoveredBySubRegs use this index, we can + // no longer assume that the lanes are covering their registers. + if (!Idx.AllSuperRegsCovered) + CoveringLanes &= ~Mask; + } + + // Compute lane mask combinations for register classes. + for (auto &RegClass : RegClasses) { + unsigned LaneMask = 0; + for (const auto &SubRegIndex : SubRegIndices) { + if (RegClass.getSubClassWithSubReg(&SubRegIndex) == nullptr) + continue; + LaneMask |= SubRegIndex.LaneMask; + } + RegClass.LaneMask = LaneMask; + } } namespace { @@ -1193,7 +1296,7 @@ namespace { // for which the unit weight equals the set weight. These units should not have // their weight increased. struct UberRegSet { - CodeGenRegister::Set Regs; + CodeGenRegister::Vec Regs; unsigned Weight; CodeGenRegister::RegUnitList SingularDeterminants; @@ -1209,22 +1312,20 @@ static void computeUberSets(std::vector &UberSets, std::vector &RegSets, CodeGenRegBank &RegBank) { - const std::vector &Registers = RegBank.getRegisters(); + const auto &Registers = RegBank.getRegisters(); // The Register EnumValue is one greater than its index into Registers. - assert(Registers.size() == Registers[Registers.size()-1]->EnumValue && + assert(Registers.size() == Registers.back().EnumValue && "register enum value mismatch"); // For simplicitly make the SetID the same as EnumValue. IntEqClasses UberSetIDs(Registers.size()+1); std::set AllocatableRegs; - for (unsigned i = 0, e = RegBank.getRegClasses().size(); i != e; ++i) { - - CodeGenRegisterClass *RegClass = RegBank.getRegClasses()[i]; - if (!RegClass->Allocatable) + for (auto &RegClass : RegBank.getRegClasses()) { + if (!RegClass.Allocatable) continue; - const CodeGenRegister::Set &Regs = RegClass->getMembers(); + const CodeGenRegister::Vec &Regs = RegClass.getMembers(); if (Regs.empty()) continue; @@ -1232,15 +1333,14 @@ 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()), - E = Regs.end(); I != E; ++I) { + for (auto I = std::next(Regs.begin()), E = Regs.end(); I != E; ++I) { AllocatableRegs.insert((*I)->EnumValue); UberSetIDs.join(USetID, (*I)->EnumValue); } } // Combine non-allocatable regs. - for (unsigned i = 0, e = Registers.size(); i != e; ++i) { - unsigned RegNum = Registers[i]->EnumValue; + for (const auto &Reg : Registers) { + unsigned RegNum = Reg.EnumValue; if (AllocatableRegs.count(RegNum)) continue; @@ -1254,17 +1354,18 @@ static void computeUberSets(std::vector &UberSets, // Insert Registers into the UberSets formed by union-find. // Do not resize after this. UberSets.resize(UberSetIDs.getNumClasses()); - for (unsigned i = 0, e = Registers.size(); i != e; ++i) { - const CodeGenRegister *Reg = Registers[i]; - unsigned USetID = UberSetIDs[Reg->EnumValue]; + unsigned i = 0; + for (const CodeGenRegister &Reg : Registers) { + unsigned USetID = UberSetIDs[Reg.EnumValue]; if (!USetID) USetID = ZeroID; else if (USetID == ZeroID) USetID = 0; UberRegSet *USet = &UberSets[USetID]; - USet->Regs.insert(Reg); - RegSets[i] = USet; + USet->Regs.push_back(&Reg); + sortAndUniqueRegisters(USet->Regs); + RegSets[i++] = USet; } } @@ -1272,11 +1373,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()) { @@ -1294,16 +1395,21 @@ 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 (auto &Unit : I->Regs) + dbgs() << " " << Unit->getName(); + dbgs() << "\n"); + // Update the set weight. + I->Weight = MaxWeight; + } // Find singular determinants. - for (CodeGenRegister::Set::iterator RegI = I->Regs.begin(), - RegE = I->Regs.end(); RegI != RegE; ++RegI) { - if ((*RegI)->getRegUnits().size() == 1 - && (*RegI)->getWeight(RegBank) == I->Weight) - mergeRegUnits(I->SingularDeterminants, (*RegI)->getRegUnits()); + for (const auto R : I->Regs) { + if (R->getRegUnits().count() == 1 && R->getWeight(RegBank) == I->Weight) { + I->SingularDeterminants |= R->getRegUnits(); + } } } } @@ -1321,13 +1427,14 @@ static void computeUberWeights(std::vector &UberSets, static bool normalizeWeight(CodeGenRegister *Reg, std::vector &UberSets, std::vector &RegSets, - std::set &NormalRegs, + SparseBitVector<> &NormalRegs, CodeGenRegister::RegUnitList &NormalUnits, CodeGenRegBank &RegBank) { - bool Changed = false; - if (!NormalRegs.insert(Reg->EnumValue).second) - return Changed; + if (NormalRegs.test(Reg->EnumValue)) + return false; + NormalRegs.set(Reg->EnumValue); + bool Changed = false; const CodeGenRegister::SubRegMap &SRM = Reg->getSubRegs(); for (CodeGenRegister::SubRegMap::const_iterator SRI = SRM.begin(), SRE = SRM.end(); SRI != SRE; ++SRI) { @@ -1351,8 +1458,8 @@ static bool normalizeWeight(CodeGenRegister *Reg, // A register unit's weight can be adjusted only if it is the singular unit // for this register, has not been used to normalize a subregister's set, // and has not already been used to singularly determine this UberRegSet. - unsigned AdjustUnit = Reg->getRegUnits().front(); - if (Reg->getRegUnits().size() != 1 + unsigned AdjustUnit = *Reg->getRegUnits().begin(); + if (Reg->getRegUnits().count() != 1 || hasRegUnit(NormalUnits, AdjustUnit) || hasRegUnit(UberSet->SingularDeterminants, AdjustUnit)) { // We don't have an adjustable unit, so adopt a new one. @@ -1370,7 +1477,7 @@ static bool normalizeWeight(CodeGenRegister *Reg, } // Mark these units normalized so superregisters can't change their weights. - mergeRegUnits(NormalUnits, Reg->getRegUnits()); + NormalUnits |= Reg->getRegUnits(); return Changed; } @@ -1393,11 +1500,11 @@ void CodeGenRegBank::computeRegUnitWeights() { for (bool Changed = true; Changed; ++NumIters) { assert(NumIters <= NumNativeRegUnits && "Runaway register unit weights"); Changed = false; - for (unsigned i = 0, e = Registers.size(); i != e; ++i) { + for (auto &Reg : Registers) { CodeGenRegister::RegUnitList NormalUnits; - std::set NormalRegs; - Changed |= normalizeWeight(Registers[i], UberSets, RegSets, - NormalRegs, NormalUnits, *this); + SparseBitVector<> NormalRegs; + Changed |= normalizeWeight(&Reg, UberSets, RegSets, NormalRegs, + NormalUnits, *this); } } } @@ -1423,7 +1530,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"); @@ -1437,9 +1560,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; } } @@ -1464,31 +1592,52 @@ 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(); - unsigned NumRegClasses = RegClasses.size(); - for (unsigned RCIdx = 0, RCEnd = NumRegClasses; RCIdx != RCEnd; ++RCIdx) { - if (!RegClasses[RCIdx]->Allocatable) + auto &RegClasses = getRegClasses(); + for (auto &RC : RegClasses) { + if (!RC.Allocatable) continue; // Speculatively grow the RegUnitSets to hold the new set. RegUnitSets.resize(RegUnitSets.size() + 1); - RegUnitSets.back().Name = RegClasses[RCIdx]->getName(); + RegUnitSets.back().Name = RC.getName(); // Compute a sorted list of units in this class. - RegClasses[RCIdx]->buildRegUnitSet(RegUnitSets.back().Units); + RC.buildRegUnitSet(RegUnitSets.back().Units); // 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 + << ":"; + for (auto &U : RegUnitSets[USIdx].Units) + dbgs() << " " << RegUnits[U].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 + << ":"; + for (auto &U : RegUnitSets[USIdx].Units) + dbgs() << " " << RegUnits[U].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) { @@ -1524,40 +1673,135 @@ 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 << ":"; + for (auto &U : RegUnitSets.back().Units) + dbgs() << " " << RegUnits[U].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 + << ":"; + for (auto &U : RegUnitSets[USIdx].Units) + dbgs() << " " << RegUnits[U].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) { - if (!RegClasses[RCIdx]->Allocatable) + RegClassUnitSets.resize(RegClasses.size()); + int RCIdx = -1; + for (auto &RC : RegClasses) { + ++RCIdx; + if (!RC.Allocatable) continue; // Recompute the sorted list of units in this class. - std::vector RegUnits; - RegClasses[RCIdx]->buildRegUnitSet(RegUnits); + std::vector RCRegUnits; + RC.buildRegUnitSet(RCRegUnits); // Don't increase pressure for unallocatable regclasses. - if (RegUnits.empty()) + if (RCRegUnits.empty()) continue; + DEBUG(dbgs() << "RC " << RC.getName() << " Units: \n"; + for (auto &U : RCRegUnits) + dbgs() << RegUnits[U].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); + } + } +} + +void CodeGenRegBank::computeRegUnitLaneMasks() { + for (auto &Register : Registers) { + // Create an initial lane mask for all register units. + const auto &RegUnits = Register.getRegUnits(); + CodeGenRegister::RegUnitLaneMaskList RegUnitLaneMasks(RegUnits.count(), 0); + // Iterate through SubRegisters. + typedef CodeGenRegister::SubRegMap SubRegMap; + const SubRegMap &SubRegs = Register.getSubRegs(); + for (SubRegMap::const_iterator S = SubRegs.begin(), + SE = SubRegs.end(); S != SE; ++S) { + CodeGenRegister *SubReg = S->second; + // Ignore non-leaf subregisters, their lane masks are fully covered by + // the leaf subregisters anyway. + if (SubReg->getSubRegs().size() != 0) + continue; + CodeGenSubRegIndex *SubRegIndex = S->first; + const CodeGenRegister *SubRegister = S->second; + unsigned LaneMask = SubRegIndex->LaneMask; + // Distribute LaneMask to Register Units touched. + for (unsigned SUI : SubRegister->getRegUnits()) { + bool Found = false; + unsigned u = 0; + for (unsigned RU : RegUnits) { + if (SUI == RU) { + RegUnitLaneMasks[u] |= LaneMask; + assert(!Found); + Found = true; + } + ++u; + } + (void)Found; + assert(Found); + } + } + Register.setRegUnitLaneMasks(RegUnitLaneMasks); + } } void CodeGenRegBank::computeDerivedInfo() { computeComposites(); + computeSubRegLaneMasks(); // Compute a weight for each register unit created during getSubRegs. // This may create adopted register units (with unit # >= NumNativeRegUnits). @@ -1566,6 +1810,33 @@ void CodeGenRegBank::computeDerivedInfo() { // Compute a unique set of RegUnitSets. One for each RegClass and inferred // supersets for the union of overlapping sets. computeRegUnitSets(); + + computeRegUnitLaneMasks(); + + // Compute register class HasDisjunctSubRegs flag. + for (CodeGenRegisterClass &RC : RegClasses) { + RC.HasDisjunctSubRegs = false; + for (const CodeGenRegister *Reg : RC.getMembers()) + RC.HasDisjunctSubRegs |= Reg->HasDisjunctSubRegs; + } + + // 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; + } } // @@ -1575,20 +1846,23 @@ void CodeGenRegBank::computeDerivedInfo() { // returns a maximal register class for all X. // void CodeGenRegBank::inferCommonSubClass(CodeGenRegisterClass *RC) { - for (unsigned rci = 0, rce = RegClasses.size(); rci != rce; ++rci) { + assert(!RegClasses.empty()); + // Stash the iterator to the last element so that this loop doesn't visit + // elements added by the getOrCreateSubClass call within it. + for (auto I = RegClasses.begin(), E = std::prev(RegClasses.end()); + I != std::next(E); ++I) { CodeGenRegisterClass *RC1 = RC; - CodeGenRegisterClass *RC2 = RegClasses[rci]; + CodeGenRegisterClass *RC2 = &*I; if (RC1 == RC2) continue; // Compute the set intersection of RC1 and RC2. - const CodeGenRegister::Set &Memb1 = RC1->getMembers(); - const CodeGenRegister::Set &Memb2 = RC2->getMembers(); - CodeGenRegister::Set Intersection; - std::set_intersection(Memb1.begin(), Memb1.end(), - Memb2.begin(), Memb2.end(), - std::inserter(Intersection, Intersection.begin()), - CodeGenRegister::Less()); + const CodeGenRegister::Vec &Memb1 = RC1->getMembers(); + const CodeGenRegister::Vec &Memb2 = RC2->getMembers(); + CodeGenRegister::Vec Intersection; + std::set_intersection( + Memb1.begin(), Memb1.end(), Memb2.begin(), Memb2.end(), + std::inserter(Intersection, Intersection.begin()), deref()); // Skip disjoint class pairs. if (Intersection.empty()) @@ -1614,37 +1888,38 @@ void CodeGenRegBank::inferCommonSubClass(CodeGenRegisterClass *RC) { // void CodeGenRegBank::inferSubClassWithSubReg(CodeGenRegisterClass *RC) { // Map SubRegIndex to set of registers in RC supporting that SubRegIndex. - typedef std::map SubReg2SetMap; + typedef std::map> SubReg2SetMap; // Compute the set of registers supporting each SubRegIndex. SubReg2SetMap SRSets; - for (CodeGenRegister::Set::const_iterator RI = RC->getMembers().begin(), - RE = RC->getMembers().end(); RI != RE; ++RI) { - const CodeGenRegister::SubRegMap &SRM = (*RI)->getSubRegs(); + for (const auto R : RC->getMembers()) { + const CodeGenRegister::SubRegMap &SRM = R->getSubRegs(); for (CodeGenRegister::SubRegMap::const_iterator I = SRM.begin(), E = SRM.end(); I != E; ++I) - SRSets[I->first].insert(*RI); + SRSets[I->first].push_back(R); } + for (auto I : SRSets) + sortAndUniqueRegisters(I.second); + // Find matching classes for all SRSets entries. Iterate in SubRegIndex // numerical order to visit synthetic indices last. - for (unsigned sri = 0, sre = SubRegIndices.size(); sri != sre; ++sri) { - CodeGenSubRegIndex *SubIdx = SubRegIndices[sri]; - SubReg2SetMap::const_iterator I = SRSets.find(SubIdx); + for (const auto &SubIdx : SubRegIndices) { + SubReg2SetMap::const_iterator I = SRSets.find(&SubIdx); // Unsupported SubRegIndex. Skip it. if (I == SRSets.end()) continue; // In most cases, all RC registers support the SubRegIndex. if (I->second.size() == RC->getMembers().size()) { - RC->setSubClassWithSubReg(SubIdx, RC); + RC->setSubClassWithSubReg(&SubIdx, RC); continue; } // This is a real subset. See if we have a matching class. CodeGenRegisterClass *SubRC = getOrCreateSubClass(RC, &I->second, RC->getName() + "_with_" + I->first->getName()); - RC->setSubClassWithSubReg(SubIdx, SubRC); + RC->setSubClassWithSubReg(&SubIdx, SubRC); } } @@ -1656,27 +1931,24 @@ void CodeGenRegBank::inferSubClassWithSubReg(CodeGenRegisterClass *RC) { // void CodeGenRegBank::inferMatchingSuperRegClass(CodeGenRegisterClass *RC, - unsigned FirstSubRegRC) { + std::list::iterator FirstSubRegRC) { SmallVector, 16> SSPairs; BitVector TopoSigs(getNumTopoSigs()); // Iterate in SubRegIndex numerical order to visit synthetic indices last. - for (unsigned sri = 0, sre = SubRegIndices.size(); sri != sre; ++sri) { - CodeGenSubRegIndex *SubIdx = SubRegIndices[sri]; + for (auto &SubIdx : SubRegIndices) { // Skip indexes that aren't fully supported by RC's registers. This was // computed by inferSubClassWithSubReg() above which should have been // called first. - if (RC->getSubClassWithSubReg(SubIdx) != RC) + if (RC->getSubClassWithSubReg(&SubIdx) != RC) continue; // Build list of (Super, Sub) pairs for this SubIdx. SSPairs.clear(); TopoSigs.reset(); - for (CodeGenRegister::Set::const_iterator RI = RC->getMembers().begin(), - RE = RC->getMembers().end(); RI != RE; ++RI) { - const CodeGenRegister *Super = *RI; - const CodeGenRegister *Sub = Super->getSubRegs().find(SubIdx)->second; + for (const auto Super : RC->getMembers()) { + const CodeGenRegister *Sub = Super->getSubRegs().find(&SubIdx)->second; assert(Sub && "Missing sub-register"); SSPairs.push_back(std::make_pair(Super, Sub)); TopoSigs.set(Sub->getTopoSig()); @@ -1684,29 +1956,36 @@ void CodeGenRegBank::inferMatchingSuperRegClass(CodeGenRegisterClass *RC, // Iterate over sub-register class candidates. Ignore classes created by // this loop. They will never be useful. - for (unsigned rci = FirstSubRegRC, rce = RegClasses.size(); rci != rce; - ++rci) { - CodeGenRegisterClass *SubRC = RegClasses[rci]; + // Store an iterator to the last element (not end) so that this loop doesn't + // visit newly inserted elements. + assert(!RegClasses.empty()); + for (auto I = FirstSubRegRC, E = std::prev(RegClasses.end()); + I != std::next(E); ++I) { + CodeGenRegisterClass &SubRC = *I; // Topological shortcut: SubRC members have the wrong shape. - if (!TopoSigs.anyCommon(SubRC->getTopoSigs())) + if (!TopoSigs.anyCommon(SubRC.getTopoSigs())) continue; // Compute the subset of RC that maps into SubRC. - CodeGenRegister::Set SubSet; + CodeGenRegister::Vec SubSetVec; for (unsigned i = 0, e = SSPairs.size(); i != e; ++i) - if (SubRC->contains(SSPairs[i].second)) - SubSet.insert(SSPairs[i].first); - if (SubSet.empty()) + if (SubRC.contains(SSPairs[i].second)) + SubSetVec.push_back(SSPairs[i].first); + + if (SubSetVec.empty()) continue; + // RC injects completely into SubRC. - if (SubSet.size() == SSPairs.size()) { - SubRC->addSuperRegClass(SubIdx, RC); + sortAndUniqueRegisters(SubSetVec); + if (SubSetVec.size() == SSPairs.size()) { + SubRC.addSuperRegClass(&SubIdx, RC); continue; } + // Only a subset of RC maps into SubRC. Make sure it is represented by a // class. - getOrCreateSubClass(RC, &SubSet, RC->getName() + - "_with_" + SubIdx->getName() + - "_in_" + SubRC->getName()); + getOrCreateSubClass(RC, &SubSetVec, RC->getName() + "_with_" + + SubIdx.getName() + "_in_" + + SubRC.getName()); } } } @@ -1716,14 +1995,19 @@ void CodeGenRegBank::inferMatchingSuperRegClass(CodeGenRegisterClass *RC, // Infer missing register classes. // void CodeGenRegBank::computeInferredRegisterClasses() { + assert(!RegClasses.empty()); // When this function is called, the register classes have not been sorted // and assigned EnumValues yet. That means getSubClasses(), // getSuperClasses(), and hasSubClass() functions are defunct. - unsigned FirstNewRC = RegClasses.size(); + + // Use one-before-the-end so it doesn't move forward when new elements are + // added. + auto FirstNewRC = std::prev(RegClasses.end()); // Visit all register classes, including the ones being added by the loop. - for (unsigned rci = 0; rci != RegClasses.size(); ++rci) { - CodeGenRegisterClass *RC = RegClasses[rci]; + // Watch out for iterator invalidation here. + for (auto I = RegClasses.begin(), E = RegClasses.end(); I != E; ++I) { + CodeGenRegisterClass *RC = &*I; // Synthesize answers for getSubClassWithSubReg(). inferSubClassWithSubReg(RC); @@ -1740,10 +2024,11 @@ void CodeGenRegBank::computeInferredRegisterClasses() { // after inferMatchingSuperRegClass was called. At this point, // inferMatchingSuperRegClass has checked SuperRC = [0..rci] with SubRC = // [0..FirstNewRC). We need to cover SubRC = [FirstNewRC..rci]. - if (rci + 1 == FirstNewRC) { - unsigned NextNewRC = RegClasses.size(); - for (unsigned rci2 = 0; rci2 != FirstNewRC; ++rci2) - inferMatchingSuperRegClass(RegClasses[rci2], FirstNewRC); + if (I == FirstNewRC) { + auto NextNewRC = std::prev(RegClasses.end()); + for (auto I2 = RegClasses.begin(), E2 = std::next(FirstNewRC); I2 != E2; + ++I2) + inferMatchingSuperRegClass(&*I2, E2); FirstNewRC = NextNewRC; } } @@ -1757,10 +2042,8 @@ void CodeGenRegBank::computeInferredRegisterClasses() { const CodeGenRegisterClass* CodeGenRegBank::getRegClassForRegister(Record *R) { const CodeGenRegister *Reg = getReg(R); - ArrayRef RCs = getRegClasses(); - const CodeGenRegisterClass *FoundRC = 0; - for (unsigned i = 0, e = RCs.size(); i != e; ++i) { - const CodeGenRegisterClass &RC = *RCs[i]; + const CodeGenRegisterClass *FoundRC = nullptr; + for (const auto &RC : getRegClasses()) { if (!RC.contains(Reg)) continue; @@ -1773,7 +2056,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, @@ -1791,7 +2074,7 @@ CodeGenRegBank::getRegClassForRegister(Record *R) { // Multiple classes, and neither is a superclass of the other. // Return null. - return 0; + return nullptr; } return FoundRC; }