[TableGen] Use SmallMapVector to simplify some code that was trying to keep a vector unique

[craig.topper]

Summary

This code previously had a SmallVector of std::pairs containing an unsigned and another SmallVector. The outer vector was using the unsigned effectively as a key to decide which SmallVector to add into. So each time something new needed to be added the out vector needed to be scanned. If it wasn't found a new entry needed to be added to be added. This sounds very much like a map, but the next loop iterates over the outer vector to get a deterministic order.

We can simplify this code greatly if use SmallMapVector instead. This uses more stack space since we now have a vector and a map, but the searching and creating new entries all happens behind the scenes. It should also make the search more efficient though usually there are only a few entries so that doesn't matter much.

We could probably get determinism by just using std::map which would iterate over the unsigned key, but that would generate different output from what we get with the current implementation.

[dblaikie]

Sounds good to me

llvm/trunk/utils/TableGen/CodeGenSchedule.cpp

 // This file defines structures to encapsulate the machine model as described in
 // the target description.
 //
 //===----------------------------------------------------------------------===//
 
 #include "CodeGenSchedule.h"
 #include "CodeGenInstruction.h"
 #include "CodeGenTarget.h"
+#include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Regex.h"
 #include "llvm/Support/raw_ostream.h"

 
 // Create classes for each set of opcodes that are in the same InstReadWrite
 // definition across all processors.
 void CodeGenSchedModels::createInstRWClass(Record *InstRWDef) {
   // ClassInstrs will hold an entry for each subset of Instrs in InstRWDef that
   // intersects with an existing class via a previous InstRWDef. Instrs that do
   // not intersect with an existing class refer back to their former class as
   // determined from ItinDef or SchedRW.
-  SmallVector<std::pair<unsigned, SmallVector<Record *, 8>>, 4> ClassInstrs;
+  SmallMapVector<unsigned, SmallVector<Record *, 8>, 4> ClassInstrs;
   // Sort Instrs into sets.
   const RecVec *InstDefs = Sets.expand(InstRWDef);
   if (InstDefs->empty())
     PrintFatalError(InstRWDef->getLoc(), "No matching instruction opcodes");
 
   for (Record *InstDef : *InstDefs) {
     InstClassMapTy::const_iterator Pos = InstrClassMap.find(InstDef);
     if (Pos == InstrClassMap.end())
       PrintFatalError(InstDef->getLoc(), "No sched class for instruction.");
     unsigned SCIdx = Pos->second;
-    unsigned CIdx = 0, CEnd = ClassInstrs.size();
-    for (; CIdx != CEnd; ++CIdx) {
-      if (ClassInstrs[CIdx].first == SCIdx)
-        break;
-    }
-    if (CIdx == CEnd) {
-      ClassInstrs.resize(CEnd + 1);
-      ClassInstrs[CIdx].first = SCIdx;
-    }
-    ClassInstrs[CIdx].second.push_back(InstDef);
+    ClassInstrs[SCIdx].push_back(InstDef);
   }
   // For each set of Instrs, create a new class if necessary, and map or remap
   // the Instrs to it.
-  for (unsigned CIdx = 0, CEnd = ClassInstrs.size(); CIdx != CEnd; ++CIdx) {
-    unsigned OldSCIdx = ClassInstrs[CIdx].first;
-    ArrayRef<Record*> InstDefs = ClassInstrs[CIdx].second;
+  for (auto &Entry : ClassInstrs) {
+    unsigned OldSCIdx = Entry.first;
+    ArrayRef<Record*> InstDefs = Entry.second;
     // If the all instrs in the current class are accounted for, then leave
     // them mapped to their old class.
     if (OldSCIdx) {
       const RecVec &RWDefs = SchedClasses[OldSCIdx].InstRWs;
       if (!RWDefs.empty()) {
         const RecVec *OrigInstDefs = Sets.expand(RWDefs[0]);
         unsigned OrigNumInstrs = 0;
         for (Record *OIDef : *OrigInstDefs) {