Replace another std::set in the core of CodeGenRegister, this time with sorted arrays.

[resistor]

Summary

The hot path through this region of code does lots of batch inserts into sets. By storing them as sorted arrays, we can defer the sorting to the end of the batch, which is dramatically more efficient. This reduces tblgen runtime by 25% on my worst-case target.

[chandlerc]

Change looks fine, but I'd really love to see this code cleaned up more if you're going to be here...

• Not using weird typedefs like Vec
• Using range based for loops rather than just auto.
• Use lambdas

Anyways, none of that cleanup should preclude making it go faster.

utils/TableGen/CodeGenRegisters.cpp

645

This should be sortRegisterVector... but it doesn't just sort, it uniques as well. I would probably call it 'sortAndUniqueRegisters', but feel free to paint it a different shade.

utils/TableGen/CodeGenRegisters.h

418–419

My clang format spidey sense says this line break isn't necessary.

[resistor]

r227682

utils/TableGen/CodeGenRegisters.h

       }
     };
 
+    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<const CodeGenRegister*, Less> Set;
+    typedef std::vector<const CodeGenRegister*> Vec;
 
   private:
     bool SubRegsComplete;

 
 
   class CodeGenRegisterClass {
-    CodeGenRegister::Set Members;
+    CodeGenRegister::Vec Members;
     // Allocation orders. Order[0] always contains all registers in Members.
     std::vector<SmallVector<Record*, 16> > Orders;
     // Bit mask of sub-classes including this, indexed by their EnumValue.

 
     // 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; }

     // 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)

 
     // 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.

utils/TableGen/CodeGenRegisters.cpp

 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) {

 //                            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()),

   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;

     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());
 }
 

 }
 
 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 << " }";
   }

 // 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);

 // 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;
 

     if (!RegClass.Allocatable)
       continue;
 
-    const CodeGenRegister::Set &Regs = RegClass.getMembers();
+    const CodeGenRegister::Vec &Regs = RegClass.getMembers();
     if (Regs.empty())
       continue;
 

     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);
     }

       USetID = 0;
 
     UberRegSet *USet = &UberSets[USetID];
-    USet->Regs.insert(&Reg);
+    USet->Regs.push_back(&Reg);
+    SortRegisterVector(USet->Regs);
     RegSets[i++] = USet;
   }
 }

     }
 
     // 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();

       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()),

 //
 void CodeGenRegBank::inferSubClassWithSubReg(CodeGenRegisterClass *RC) {
   // Map SubRegIndex to set of registers in RC supporting that SubRegIndex.
-  typedef std::map<const CodeGenSubRegIndex *, CodeGenRegister::Set,
+  typedef std::map<const CodeGenSubRegIndex *, CodeGenRegister::Vec,
                    CodeGenSubRegIndex::Less> 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) {

     // 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");

       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_" +
     }
   }
 }

utils/TableGen/RegisterInfoEmitter.cpp

      << "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 {