Index: utils/TableGen/CodeGenRegisters.h =================================================================== --- utils/TableGen/CodeGenRegisters.h +++ utils/TableGen/CodeGenRegisters.h @@ -241,8 +241,16 @@ } }; + struct Equal { + bool operator()(const CodeGenRegister *A, + const CodeGenRegister *B) const { + assert(A && B); + return A->EnumValue == B->EnumValue; + } + }; + // Canonically ordered set. - typedef std::set Set; + typedef std::vector Vec; private: bool SubRegsComplete; @@ -268,7 +276,7 @@ class CodeGenRegisterClass { - CodeGenRegister::Set Members; + CodeGenRegister::Vec Members; // Allocation orders. Order[0] always contains all registers in Members. std::vector > Orders; // Bit mask of sub-classes including this, indexed by their EnumValue. @@ -389,7 +397,7 @@ // Get the set of registers. This set contains the same registers as // getOrder(0). - const CodeGenRegister::Set &getMembers() const { return Members; } + const CodeGenRegister::Vec &getMembers() const { return Members; } // Get a bit vector of TopoSigs present in this register class. const BitVector &getTopoSigs() const { return TopoSigs; } @@ -403,11 +411,12 @@ // sub-classes. Note the ordering provided by this key is not the same as // the topological order used for the EnumValues. struct Key { - const CodeGenRegister::Set *Members; + const CodeGenRegister::Vec *Members; unsigned SpillSize; unsigned SpillAlignment; - Key(const CodeGenRegister::Set *M, unsigned S = 0, unsigned A = 0) + Key(const CodeGenRegister::Vec *M, + unsigned S = 0, unsigned A = 0) : Members(M), SpillSize(S), SpillAlignment(A) {} Key(const CodeGenRegisterClass &RC) @@ -525,7 +534,7 @@ // Create a synthetic sub-class if it is missing. CodeGenRegisterClass *getOrCreateSubClass(const CodeGenRegisterClass *RC, - const CodeGenRegister::Set *Membs, + const CodeGenRegister::Vec *Membs, StringRef Name); // Infer missing register classes. Index: utils/TableGen/CodeGenRegisters.cpp =================================================================== --- utils/TableGen/CodeGenRegisters.cpp +++ utils/TableGen/CodeGenRegisters.cpp @@ -152,11 +152,11 @@ namespace { // Iterate over all register units in a set of registers. class RegUnitIterator { - CodeGenRegister::Set::const_iterator RegI, RegE; + 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) { @@ -642,6 +642,11 @@ // CodeGenRegisterClass //===----------------------------------------------------------------------===// +static void SortRegisterVector(CodeGenRegister::Vec &M) { + std::sort(M.begin(), M.end(), CodeGenRegister::Less()); + M.erase(std::unique(M.begin(), M.end(), CodeGenRegister::Equal()), M.end()); +} + CodeGenRegisterClass::CodeGenRegisterClass(CodeGenRegBank &RegBank, Record *R) : TheDef(R), Name(R->getName()), @@ -675,9 +680,10 @@ 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()); } + SortRegisterVector(Members); // Alternative allocation orders may be subsets. SetTheory::RecSet Order; @@ -719,8 +725,7 @@ SpillAlignment(Props.SpillAlignment), CopyCost(0), Allocatable(true) { - for (CodeGenRegister::Set::iterator I = Members.begin(), E = Members.end(); - I != E; ++I) + for (auto I = Members.begin(), E = Members.end(); I != E; ++I) TopoSigs.set((*I)->getTopoSig()); } @@ -750,14 +755,14 @@ } bool CodeGenRegisterClass::contains(const CodeGenRegister *Reg) const { - return Members.count(Reg); + return std::binary_search(Members.begin(), Members.end(), Reg, + CodeGenRegister::Less()); } 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) + for (auto I = K.Members->begin(), E = K.Members->end(); I != E; ++I) OS << ", " << (*I)->getName(); return OS << " }"; } @@ -1034,7 +1039,7 @@ // 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); @@ -1283,7 +1288,7 @@ // 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; @@ -1312,7 +1317,7 @@ if (!RegClass.Allocatable) continue; - const CodeGenRegister::Set &Regs = RegClass.getMembers(); + const CodeGenRegister::Vec &Regs = RegClass.getMembers(); if (Regs.empty()) continue; @@ -1320,8 +1325,7 @@ assert(USetID && "register number 0 is invalid"); AllocatableRegs.insert((*Regs.begin())->EnumValue); - for (CodeGenRegister::Set::const_iterator I = std::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); } @@ -1351,7 +1355,8 @@ USetID = 0; UberRegSet *USet = &UberSets[USetID]; - USet->Regs.insert(&Reg); + USet->Regs.push_back(&Reg); + SortRegisterVector(USet->Regs); RegSets[i++] = USet; } } @@ -1393,8 +1398,8 @@ } // Find singular determinants. - for (CodeGenRegister::Set::iterator RegI = I->Regs.begin(), - RegE = I->Regs.end(); RegI != RegE; ++RegI) { + for (auto RegI = I->Regs.begin(), RegE = I->Regs.end(); + RegI != RegE; ++RegI) { if ((*RegI)->getRegUnits().count() == 1 && (*RegI)->getWeight(RegBank) == I->Weight) { I->SingularDeterminants |= (*RegI)->getRegUnits(); @@ -1837,9 +1842,9 @@ continue; // Compute the set intersection of RC1 and RC2. - const CodeGenRegister::Set &Memb1 = RC1->getMembers(); - const CodeGenRegister::Set &Memb2 = RC2->getMembers(); - CodeGenRegister::Set Intersection; + 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()), @@ -1869,19 +1874,22 @@ // void CodeGenRegBank::inferSubClassWithSubReg(CodeGenRegisterClass *RC) { // Map SubRegIndex to set of registers in RC supporting that SubRegIndex. - 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) { + for (auto RI = RC->getMembers().begin(), RE = RC->getMembers().end(); + RI != RE; ++RI) { const CodeGenRegister::SubRegMap &SRM = (*RI)->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(*RI); } + for (auto I : SRSets) + SortRegisterVector(I.second); + // Find matching classes for all SRSets entries. Iterate in SubRegIndex // numerical order to visit synthetic indices last. for (const auto &SubIdx : SubRegIndices) { @@ -1926,8 +1934,8 @@ // 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) { + for (auto RI = RC->getMembers().begin(), RE = RC->getMembers().end(); + RI != RE; ++RI) { const CodeGenRegister *Super = *RI; const CodeGenRegister *Sub = Super->getSubRegs().find(&SubIdx)->second; assert(Sub && "Missing sub-register"); @@ -1947,22 +1955,26 @@ 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()) + SubSetVec.push_back(SSPairs[i].first); + + if (SubSetVec.empty()) continue; + // RC injects completely into SubRC. - if (SubSet.size() == SSPairs.size()) { + SortRegisterVector(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()); } } } Index: utils/TableGen/RegisterInfoEmitter.cpp =================================================================== --- utils/TableGen/RegisterInfoEmitter.cpp +++ utils/TableGen/RegisterInfoEmitter.cpp @@ -180,7 +180,7 @@ << "getRegClassWeight(const TargetRegisterClass *RC) const {\n" << " static const RegClassWeight RCWeightTable[] = {\n"; for (const auto &RC : RegBank.getRegClasses()) { - const CodeGenRegister::Set &Regs = RC.getMembers(); + const CodeGenRegister::Vec &Regs = RC.getMembers(); if (Regs.empty()) OS << " {0, 0"; else {