[TableGen] Change std::sort to llvm::sort in response to r327219

[mgrang]

Summary

r327219 added wrappers to std::sort which randomly shuffle the container before sorting.
This will help in uncovering non-determinism caused due to undefined sorting
order of objects having the same key.

To make use of that infrastructure we need to invoke llvm::sort instead of std::sort.

Note: This patch is one of a series of patches to replace *all* std::sort to llvm::sort.
Refer the comments section in D44363 for a list of all the required patches.

[dsanders]

LGTM

llvm/trunk/lib/TableGen/Record.cpp

if (UnsortedClasses.empty()) {
     return &AnyRecord;
   }
 
   FoldingSet<RecordRecTy> &ThePool =
       UnsortedClasses[0]->getRecords().RecordTypePool;
 
   SmallVector<Record *, 4> Classes(UnsortedClasses.begin(),
                                    UnsortedClasses.end());
-  std::sort(Classes.begin(), Classes.end(),
+  llvm::sort(Classes.begin(), Classes.end(),
              [](Record *LHS, Record *RHS) {
                return LHS->getNameInitAsString() < RHS->getNameInitAsString();
              });
 
   FoldingSetNodeID ID;
   ProfileRecordRecTy(ID, Classes);
 
   void *IP = nullptr;
   if (RecordRecTy *Ty = ThePool.FindNodeOrInsertPos(ID, IP))
     return Ty;
 

llvm/trunk/utils/TableGen/CTagsEmitter.cpp

void CTagsEmitter::run(raw_ostream &OS) {
   std::vector<Tag> Tags;
   // Collect tags.
   Tags.reserve(Classes.size() + Defs.size());
   for (const auto &C : Classes)
     Tags.push_back(Tag(C.first, locate(C.second.get())));
   for (const auto &D : Defs)
     Tags.push_back(Tag(D.first, locate(D.second.get())));
   // Emit tags.
-  std::sort(Tags.begin(), Tags.end());
+  llvm::sort(Tags.begin(), Tags.end());
   OS << "!_TAG_FILE_FORMAT\t1\t/original ctags format/\n";
   OS << "!_TAG_FILE_SORTED\t1\t/0=unsorted, 1=sorted, 2=foldcase/\n";
   for (const Tag &T : Tags)
     T.emit(OS);
 }
 
 namespace llvm {
 
 void EmitCTags(RecordKeeper &RK, raw_ostream &OS) { CTagsEmitter(RK).run(OS); }
 
 } // End llvm namespace.

llvm/trunk/utils/TableGen/CodeGenDAGPatterns.cpp

 
 /// getPredicateCheck - Return a single string containing all of this
 /// pattern's predicates concatenated with "&&" operators.
 ///
 std::string PatternToMatch::getPredicateCheck() const {
   SmallVector<const Predicate*,4> PredList;
   for (const Predicate &P : Predicates)
     PredList.push_back(&P);
-  std::sort(PredList.begin(), PredList.end(), deref<llvm::less>());
+  llvm::sort(PredList.begin(), PredList.end(), deref<llvm::less>());
 
   std::string Check;
   for (unsigned i = 0, e = PredList.size(); i != e; ++i) {
     if (i != 0)
       Check += " && ";
     Check += '(' + PredList[i]->getCondString() + ')';
   }
   return Check;
std::vector<Predicate> CodeGenDAGPatterns::makePredList(ListInit *L) {
   for (Init *I : L->getValues()) {
     if (DefInit *Pred = dyn_cast<DefInit>(I))
       Preds.push_back(Pred->getDef());
     else
       llvm_unreachable("Non-def on the list");
   }
 
   // Sort so that different orders get canonicalized to the same string.
-  std::sort(Preds.begin(), Preds.end());
+  llvm::sort(Preds.begin(), Preds.end());
   return Preds;
 }
 
 void CodeGenDAGPatterns::AddPatternToMatch(TreePattern *Pattern,
                                            PatternToMatch &&PTM) {
   // Do some sanity checking on the pattern we're about to match.
   std::string Reason;
   if (!PTM.getSrcPattern()->canPatternMatch(Reason, *this)) {

llvm/trunk/utils/TableGen/CodeGenRegisters.cpp

 
 } // end anonymous namespace
 
 //===----------------------------------------------------------------------===//
 //                            CodeGenRegisterClass
 //===----------------------------------------------------------------------===//
 
 static void sortAndUniqueRegisters(CodeGenRegister::Vec &M) {
-  std::sort(M.begin(), M.end(), deref<llvm::less>());
+  llvm::sort(M.begin(), M.end(), deref<llvm::less>());
   M.erase(std::unique(M.begin(), M.end(), deref<llvm::equal>()), M.end());
 }
 
 CodeGenRegisterClass::CodeGenRegisterClass(CodeGenRegBank &RegBank, Record *R)
   : TheDef(R),
     Name(R->getName()),
     TopoSigs(RegBank.getNumTopoSigs()),
     EnumValue(-1) {
CodeGenRegisterClass::getMatchingSubClassWithSubRegs(
   CodeGenRegisterClass *BiggestSuperRegRC = getSubClassWithSubReg(SubIdx);
   if (!BiggestSuperRegRC)
     return None;
   BitVector SuperRegRCsBV = BiggestSuperRegRC->getSubClasses();
   std::vector<CodeGenRegisterClass *> SuperRegRCs;
   for (auto &RC : RegClasses)
     if (SuperRegRCsBV[RC.EnumValue])
       SuperRegRCs.emplace_back(&RC);
-  std::sort(SuperRegRCs.begin(), SuperRegRCs.end(), SizeOrder);
+  llvm::sort(SuperRegRCs.begin(), SuperRegRCs.end(), SizeOrder);
   assert(SuperRegRCs.front() == BiggestSuperRegRC && "Biggest class wasn't first");
 
   // Find all the subreg classes and order them by size too.
   std::vector<std::pair<CodeGenRegisterClass *, BitVector>> SuperRegClasses;
   for (auto &RC: RegClasses) {
     BitVector SuperRegClassesBV(RegClasses.size());
     RC.getSuperRegClasses(SubIdx, SuperRegClassesBV);
     if (SuperRegClassesBV.any())
       SuperRegClasses.push_back(std::make_pair(&RC, SuperRegClassesBV));
   }
-  std::sort(SuperRegClasses.begin(), SuperRegClasses.end(),
+  llvm::sort(SuperRegClasses.begin(), SuperRegClasses.end(),
              [&](const std::pair<CodeGenRegisterClass *, BitVector> &A,
                  const std::pair<CodeGenRegisterClass *, BitVector> &B) {
                return SizeOrder(A.first, B.first);
              });
 
   // Find the biggest subclass and subreg class such that R:subidx is in the
   // subreg class for all R in subclass.
   //
   // For example:
   // All registers in X86's GR64 have a sub_32bit subregister but no class
   // exists that contains all the 32-bit subregisters because GR64 contains RIP
   // but GR32 does not contain EIP. Instead, we constrain SuperRegRC to

 void CodeGenRegisterClass::buildRegUnitSet(const CodeGenRegBank &RegBank,
   std::vector<unsigned> &RegUnits) const {
   std::vector<unsigned> TmpUnits;
   for (RegUnitIterator UnitI(Members); UnitI.isValid(); ++UnitI) {
     const RegUnit &RU = RegBank.getRegUnit(*UnitI);
     if (!RU.Artificial)
       TmpUnits.push_back(*UnitI);
   }
-  std::sort(TmpUnits.begin(), TmpUnits.end());
+  llvm::sort(TmpUnits.begin(), TmpUnits.end());
   std::unique_copy(TmpUnits.begin(), TmpUnits.end(),
                    std::back_inserter(RegUnits));
 }
 
 //===----------------------------------------------------------------------===//
 //                               CodeGenRegBank
 //===----------------------------------------------------------------------===//
 
 CodeGenRegBank::CodeGenRegBank(RecordKeeper &Records,
                                const CodeGenHwModes &Modes) : CGH(Modes) {
   // Configure register Sets to understand register classes and tuples.
   Sets.addFieldExpander("RegisterClass", "MemberList");
   Sets.addFieldExpander("CalleeSavedRegs", "SaveList");
   Sets.addExpander("RegisterTuples", llvm::make_unique<TupleExpander>());
 
   // Read in the user-defined (named) sub-register indices.
   // More indices will be synthesized later.
   std::vector<Record*> SRIs = Records.getAllDerivedDefinitions("SubRegIndex");
-  std::sort(SRIs.begin(), SRIs.end(), LessRecord());
+  llvm::sort(SRIs.begin(), SRIs.end(), LessRecord());
   for (unsigned i = 0, e = SRIs.size(); i != e; ++i)
     getSubRegIdx(SRIs[i]);
   // Build composite maps from ComposedOf fields.
   for (auto &Idx : SubRegIndices)
     Idx.updateComponents(*this);
 
   // Read in the register definitions.
   std::vector<Record*> Regs = Records.getAllDerivedDefinitions("Register");
-  std::sort(Regs.begin(), Regs.end(), LessRecordRegister());
+  llvm::sort(Regs.begin(), Regs.end(), LessRecordRegister());
   // Assign the enumeration values.
   for (unsigned i = 0, e = Regs.size(); i != e; ++i)
     getReg(Regs[i]);
 
   // Expand tuples and number the new registers.
   std::vector<Record*> Tups =
     Records.getAllDerivedDefinitions("RegisterTuples");
 
   for (Record *R : Tups) {
     std::vector<Record *> TupRegs = *Sets.expand(R);
-    std::sort(TupRegs.begin(), TupRegs.end(), LessRecordRegister());
+    llvm::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 (auto &Reg : Registers)
     Reg.buildObjectGraph(*this);

llvm/trunk/utils/TableGen/CodeGenSchedule.cpp

void CodeGenSchedModels::collectOptionalProcessorInfo() {
 
   // Collect processor RetireControlUnit descriptors if available.
   collectRetireControlUnits();
 }
 
 /// Gather all processor models.
 void CodeGenSchedModels::collectProcModels() {
   RecVec ProcRecords = Records.getAllDerivedDefinitions("Processor");
-  std::sort(ProcRecords.begin(), ProcRecords.end(), LessRecordFieldName());
+  llvm::sort(ProcRecords.begin(), ProcRecords.end(), LessRecordFieldName());
 
   // Reserve space because we can. Reallocation would be ok.
   ProcModels.reserve(ProcRecords.size()+1);
 
   // Use idx=0 for NoModel/NoItineraries.
   Record *NoModelDef = Records.getDef("NoSchedModel");
   Record *NoItinsDef = Records.getDef("NoItineraries");
   ProcModels.emplace_back(0, "NoSchedModel", NoModelDef, NoItinsDef);
for (Record *RWDef : RWDefs) {
         assert(RWDef->isSubClassOf("SchedRead") && "Unknown SchedReadWrite");
         scanSchedRW(RWDef, SRDefs, RWSet);
       }
     }
   }
   // Find all ReadWrites referenced by SchedAlias. AliasDefs needs to be sorted
   // for the loop below that initializes Alias vectors.
   RecVec AliasDefs = Records.getAllDerivedDefinitions("SchedAlias");
-  std::sort(AliasDefs.begin(), AliasDefs.end(), LessRecord());
+  llvm::sort(AliasDefs.begin(), AliasDefs.end(), LessRecord());
   for (Record *ADef : AliasDefs) {
     Record *MatchDef = ADef->getValueAsDef("MatchRW");
     Record *AliasDef = ADef->getValueAsDef("AliasRW");
     if (MatchDef->isSubClassOf("SchedWrite")) {
       if (!AliasDef->isSubClassOf("SchedWrite"))
         PrintFatalError(ADef->getLoc(), "SchedWrite Alias must be SchedWrite");
       scanSchedRW(AliasDef, SWDefs, RWSet);
     }
     else {
       assert(MatchDef->isSubClassOf("SchedRead") && "Unknown SchedReadWrite");
       if (!AliasDef->isSubClassOf("SchedRead"))
         PrintFatalError(ADef->getLoc(), "SchedRead Alias must be SchedRead");
       scanSchedRW(AliasDef, SRDefs, RWSet);
     }
   }
   // Sort and add the SchedReadWrites directly referenced by instructions or
   // itinerary resources. Index reads and writes in separate domains.
-  std::sort(SWDefs.begin(), SWDefs.end(), LessRecord());
+  llvm::sort(SWDefs.begin(), SWDefs.end(), LessRecord());
   for (Record *SWDef : SWDefs) {
     assert(!getSchedRWIdx(SWDef, /*IsRead=*/false) && "duplicate SchedWrite");
     SchedWrites.emplace_back(SchedWrites.size(), SWDef);
   }
-  std::sort(SRDefs.begin(), SRDefs.end(), LessRecord());
+  llvm::sort(SRDefs.begin(), SRDefs.end(), LessRecord());
   for (Record *SRDef : SRDefs) {
     assert(!getSchedRWIdx(SRDef, /*IsRead-*/true) && "duplicate SchedWrite");
     SchedReads.emplace_back(SchedReads.size(), SRDef);
   }
   // Initialize WriteSequence vectors.
   for (CodeGenSchedRW &CGRW : SchedWrites) {
     if (!CGRW.IsSequence)
       continue;
if (!Inst->TheDef->isValueUnset("SchedRW"))
       findRWs(Inst->TheDef->getValueAsListOfDefs("SchedRW"), Writes, Reads);
 
     // ProcIdx == 0 indicates the class applies to all processors.
     unsigned SCIdx = addSchedClass(ItinDef, Writes, Reads, /*ProcIndices*/{0});
     InstrClassMap[Inst->TheDef] = SCIdx;
   }
   // Create classes for InstRW defs.
   RecVec InstRWDefs = Records.getAllDerivedDefinitions("InstRW");
-  std::sort(InstRWDefs.begin(), InstRWDefs.end(), LessRecord());
+  llvm::sort(InstRWDefs.begin(), InstRWDefs.end(), LessRecord());
   DEBUG(dbgs() << "\n+++ SCHED CLASSES (createInstRWClass) +++\n");
   for (Record *RWDef : InstRWDefs)
     createInstRWClass(RWDef);
 
   NumInstrSchedClasses = SchedClasses.size();
 
   bool EnableDump = false;
   DEBUG(EnableDump = true);
DEBUG(
                  << SchedClasses[i].Name << '\n';
       });
   }
 }
 
 // Gather the read/write types for each itinerary class.
 void CodeGenSchedModels::collectProcItinRW() {
   RecVec ItinRWDefs = Records.getAllDerivedDefinitions("ItinRW");
-  std::sort(ItinRWDefs.begin(), ItinRWDefs.end(), LessRecord());
+  llvm::sort(ItinRWDefs.begin(), ItinRWDefs.end(), LessRecord());
   for (Record *RWDef  : ItinRWDefs) {
     if (!RWDef->getValueInit("SchedModel")->isComplete())
       PrintFatalError(RWDef->getLoc(), "SchedModel is undefined");
     Record *ModelDef = RWDef->getValueAsDef("SchedModel");
     ProcModelMapTy::const_iterator I = ProcModelMap.find(ModelDef);
     if (I == ProcModelMap.end()) {
       PrintFatalError(RWDef->getLoc(), "Undefined SchedMachineModel "
                     + ModelDef->getName());
for (Record *PRU : Records.getAllDerivedDefinitions("ProcResourceUnits")) {
     if (!PRU->getValueInit("SchedModel")->isComplete())
       continue;
     CodeGenProcModel &PM = getProcModel(PRU->getValueAsDef("SchedModel"));
     if (!is_contained(PM.ProcResourceDefs, PRU))
       PM.ProcResourceDefs.push_back(PRU);
   }
   // Finalize each ProcModel by sorting the record arrays.
   for (CodeGenProcModel &PM : ProcModels) {
-    std::sort(PM.WriteResDefs.begin(), PM.WriteResDefs.end(),
+    llvm::sort(PM.WriteResDefs.begin(), PM.WriteResDefs.end(),
                LessRecord());
-    std::sort(PM.ReadAdvanceDefs.begin(), PM.ReadAdvanceDefs.end(),
+    llvm::sort(PM.ReadAdvanceDefs.begin(), PM.ReadAdvanceDefs.end(),
                LessRecord());
-    std::sort(PM.ProcResourceDefs.begin(), PM.ProcResourceDefs.end(),
+    llvm::sort(PM.ProcResourceDefs.begin(), PM.ProcResourceDefs.end(),
                LessRecord());
     DEBUG(
       PM.dump();
       dbgs() << "WriteResDefs: ";
       for (RecIter RI = PM.WriteResDefs.begin(),
              RE = PM.WriteResDefs.end(); RI != RE; ++RI) {
         if ((*RI)->isSubClassOf("WriteRes"))
           dbgs() << (*RI)->getValueAsDef("WriteType")->getName() << " ";
         else

llvm/trunk/utils/TableGen/CodeGenTarget.cpp

 CodeGenRegBank &CodeGenTarget::getRegBank() const {
   if (!RegBank)
     RegBank = llvm::make_unique<CodeGenRegBank>(Records, getHwModes());
   return *RegBank;
 }
 
 void CodeGenTarget::ReadRegAltNameIndices() const {
   RegAltNameIndices = Records.getAllDerivedDefinitions("RegAltNameIndex");
-  std::sort(RegAltNameIndices.begin(), RegAltNameIndices.end(), LessRecord());
+  llvm::sort(RegAltNameIndices.begin(), RegAltNameIndices.end(), LessRecord());
 }
 
 /// getRegisterByName - If there is a register with the specific AsmName,
 /// return it.
 const CodeGenRegister *CodeGenTarget::getRegisterByName(StringRef Name) const {
   const StringMap<CodeGenRegister*> &Regs = getRegBank().getRegistersByName();
   StringMap<CodeGenRegister*>::const_iterator I = Regs.find(Name);
   if (I == Regs.end())
     return nullptr;
   return I->second;
 }
 
 std::vector<ValueTypeByHwMode> CodeGenTarget::getRegisterVTs(Record *R)
       const {
   const CodeGenRegister *Reg = getRegBank().getReg(R);
   std::vector<ValueTypeByHwMode> Result;
   for (const auto &RC : getRegBank().getRegClasses()) {
     if (RC.contains(Reg)) {
       ArrayRef<ValueTypeByHwMode> InVTs = RC.getValueTypes();
       Result.insert(Result.end(), InVTs.begin(), InVTs.end());
     }
   }
 
   // Remove duplicates.
-  std::sort(Result.begin(), Result.end());
+  llvm::sort(Result.begin(), Result.end());
   Result.erase(std::unique(Result.begin(), Result.end()), Result.end());
   return Result;
 }
 
 
 void CodeGenTarget::ReadLegalValueTypes() const {
   for (const auto &RC : getRegBank().getRegClasses())
     LegalValueTypes.insert(LegalValueTypes.end(), RC.VTs.begin(), RC.VTs.end());
 
   // Remove duplicates.
-  std::sort(LegalValueTypes.begin(), LegalValueTypes.end());
+  llvm::sort(LegalValueTypes.begin(), LegalValueTypes.end());
   LegalValueTypes.erase(std::unique(LegalValueTypes.begin(),
                                     LegalValueTypes.end()),
                         LegalValueTypes.end());
 }
 
 CodeGenSchedModels &CodeGenTarget::getSchedModels() const {
   if (!SchedModels)
     SchedModels = llvm::make_unique<CodeGenSchedModels>(Records, *this);
for (const auto &I : Insts) {
     if (CGI->Namespace != "TargetOpcode")
       InstrsByEnum.push_back(CGI);
   }
 
   assert(InstrsByEnum.size() == Insts.size() && "Missing predefined instr");
 
   // All of the instructions are now in random order based on the map iteration.
   // Sort them by name.
-  std::sort(InstrsByEnum.begin() + EndOfPredefines, InstrsByEnum.end(),
-            [](const CodeGenInstruction *Rec1, const CodeGenInstruction *Rec2) {
+  llvm::sort(InstrsByEnum.begin() + EndOfPredefines, InstrsByEnum.end(),
+             [](const CodeGenInstruction *Rec1,
+                const CodeGenInstruction *Rec2) {
     return Rec1->TheDef->getName() < Rec2->TheDef->getName();
   });
 }
 
 
 /// isLittleEndianEncoding - Return whether this target encodes its instruction
 /// in little-endian format, i.e. bits laid out in the order [0..n]
 ///
CodeGenIntrinsicTable::CodeGenIntrinsicTable(const RecordKeeper &RC,
 
   Intrinsics.reserve(Defs.size());
 
   for (unsigned I = 0, e = Defs.size(); I != e; ++I) {
     bool isTarget = Defs[I]->getValueAsBit("isTarget");
     if (isTarget == TargetOnly)
       Intrinsics.push_back(CodeGenIntrinsic(Defs[I]));
   }
-  std::sort(Intrinsics.begin(), Intrinsics.end(),
+  llvm::sort(Intrinsics.begin(), Intrinsics.end(),
              [](const CodeGenIntrinsic &LHS, const CodeGenIntrinsic &RHS) {
                return std::tie(LHS.TargetPrefix, LHS.Name) <
                       std::tie(RHS.TargetPrefix, RHS.Name);
              });
   Targets.push_back({"", 0, 0});
   for (size_t I = 0, E = Intrinsics.size(); I < E; ++I)
     if (Intrinsics[I].TargetPrefix != Targets.back().Name) {
       Targets.back().Count = I - Targets.back().Offset;
       Targets.push_back({Intrinsics[I].TargetPrefix, I, 0});
     }
   Targets.back().Count = Intrinsics.size() - Targets.back().Offset;
 }
for (unsigned i = 0, e = PropList->size(); i != e; ++i) {
     } else
       llvm_unreachable("Unknown property!");
   }
 
   // Also record the SDPatternOperator Properties.
   Properties = parseSDPatternOperatorProperties(R);
 
   // Sort the argument attributes for later benefit.
-  std::sort(ArgumentAttributes.begin(), ArgumentAttributes.end());
+  llvm::sort(ArgumentAttributes.begin(), ArgumentAttributes.end());
 }
 

llvm/trunk/utils/TableGen/DAGISelEmitter.cpp

void DAGISelEmitter::run(raw_ostream &OS) {
   // Add all the patterns to a temporary list so we can sort them.
   std::vector<const PatternToMatch*> Patterns;
   for (CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(), E = CGP.ptm_end();
        I != E; ++I)
     Patterns.push_back(&*I);
 
   // We want to process the matches in order of minimal cost.  Sort the patterns
   // so the least cost one is at the start.
-  std::sort(Patterns.begin(), Patterns.end(), PatternSortingPredicate(CGP));
+  llvm::sort(Patterns.begin(), Patterns.end(), PatternSortingPredicate(CGP));
 
 
   // Convert each variant of each pattern into a Matcher.
   std::vector<Matcher*> PatternMatchers;
   for (unsigned i = 0, e = Patterns.size(); i != e; ++i) {
     for (unsigned Variant = 0; ; ++Variant) {
       if (Matcher *M = ConvertPatternToMatcher(*Patterns[i], Variant, CGP))
         PatternMatchers.push_back(M);

llvm/trunk/utils/TableGen/FastISelEmitter.cpp

for (OperandsOpcodeTypeRetPredMap::const_iterator OI = SimplePatterns.begin(),
     // If there are any forms of this signature available that operate on
     // constrained forms of the immediate (e.g., 32-bit sext immediate in a
     // 64-bit operand), check them first.
 
     std::map<OperandsSignature, std::vector<OperandsSignature> >::iterator MI
       = SignaturesWithConstantForms.find(Operands);
     if (MI != SignaturesWithConstantForms.end()) {
       // Unique any duplicates out of the list.
-      std::sort(MI->second.begin(), MI->second.end());
+      llvm::sort(MI->second.begin(), MI->second.end());
       MI->second.erase(std::unique(MI->second.begin(), MI->second.end()),
                        MI->second.end());
 
       // Check each in order it was seen.  It would be nice to have a good
       // relative ordering between them, but we're not going for optimality
       // here.
       for (unsigned i = 0, e = MI->second.size(); i != e; ++i) {
         OS << "  if (";

llvm/trunk/utils/TableGen/GlobalISelEmitter.cpp

if (Ty.isPointer() && Ty.getSizeInBits() > 0) {
          << Ty.getSizeInBits() << ")";
       return;
     }
     llvm_unreachable("Unhandled LLT");
   }
 
   const LLT &get() const { return Ty; }
 
-  /// This ordering is used for std::unique() and std::sort(). There's no
+  /// This ordering is used for std::unique() and llvm::sort(). There's no
   /// particular logic behind the order but either A < B or B < A must be
   /// true if A != B.
   bool operator<(const LLTCodeGen &Other) const {
     if (Ty.isValid() != Other.Ty.isValid())
       return Ty.isValid() < Other.Ty.isValid();
     if (!Ty.isValid())
       return false;
 
if (I->mayLoad || I->mayStore) {
       //       some other means of having a memoperand. Also limit this to
       //       emitted instructions that expect to have a memoperand too. For
       //       example, (G_SEXT (G_LOAD x)) that results in separate load and
       //       sign-extend instructions shouldn't put the memoperand on the
       //       sign-extend since it has no effect there.
       std::vector<unsigned> MergeInsnIDs;
       for (const auto &IDMatcherPair : Rule.defined_insn_vars())
         MergeInsnIDs.push_back(IDMatcherPair.second);
-      std::sort(MergeInsnIDs.begin(), MergeInsnIDs.end());
+      llvm::sort(MergeInsnIDs.begin(), MergeInsnIDs.end());
       for (const auto &MergeInsnID : MergeInsnIDs)
         Table << MatchTable::IntValue(MergeInsnID);
       Table << MatchTable::NamedValue("GIU_MergeMemOperands_EndOfList")
             << MatchTable::LineBreak;
     }
 
     // FIXME: This is a hack but it's sufficient for ISel. We'll need to do
     //        better for combines. Particularly when there are multiple match
if (InsnVariableIDs.size() >= 2) {
     for (const auto &Pair : InsnVariableIDs) {
       // Skip the root node since it isn't moving anywhere. Everything else is
       // sinking to meet it.
       if (Pair.first == Matchers.front().get())
         continue;
 
       InsnIDs.push_back(Pair.second);
     }
-    std::sort(InsnIDs.begin(), InsnIDs.end());
+    llvm::sort(InsnIDs.begin(), InsnIDs.end());
 
     for (const auto &InsnID : InsnIDs) {
       // Reject the difficult cases until we have a more accurate check.
       Table << MatchTable::Opcode("GIM_CheckIsSafeToFold")
             << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
             << MatchTable::LineBreak;
 
       // FIXME: Emit checks to determine it's _actually_ safe to fold and/or
void GlobalISelEmitter::run(raw_ostream &OS) {
 
   // Comparison function to order records by name.
   auto orderByName = [](const Record *A, const Record *B) {
     return A->getName() < B->getName();
   };
 
   std::vector<Record *> ComplexPredicates =
       RK.getAllDerivedDefinitions("GIComplexOperandMatcher");
-  std::sort(ComplexPredicates.begin(), ComplexPredicates.end(), orderByName);
+  llvm::sort(ComplexPredicates.begin(), ComplexPredicates.end(), orderByName);
 
   std::vector<Record *> CustomRendererFns =
       RK.getAllDerivedDefinitions("GICustomOperandRenderer");
-  std::sort(CustomRendererFns.begin(), CustomRendererFns.end(), orderByName);
+  llvm::sort(CustomRendererFns.begin(), CustomRendererFns.end(), orderByName);
 
   unsigned MaxTemporaries = 0;
   for (const auto &Rule : Rules)
     MaxTemporaries = std::max(MaxTemporaries, Rule.countRendererFns());
 
   OS << "#ifdef GET_GLOBALISEL_PREDICATE_BITSET\n"
      << "const unsigned MAX_SUBTARGET_PREDICATES = " << SubtargetFeatures.size()
      << ";\n"
SubtargetFeatureInfo::emitComputeAvailableFeatures(
       "computeAvailableFunctionFeatures", FunctionFeatures, OS,
       "const MachineFunction *MF");
 
   // Emit a table containing the LLT objects needed by the matcher and an enum
   // for the matcher to reference them with.
   std::vector<LLTCodeGen> TypeObjects;
   for (const auto &Ty : LLTOperandMatcher::KnownTypes)
     TypeObjects.push_back(Ty);
-  std::sort(TypeObjects.begin(), TypeObjects.end());
+  llvm::sort(TypeObjects.begin(), TypeObjects.end());
   OS << "// LLT Objects.\n"
      << "enum {\n";
   for (const auto &TypeObject : TypeObjects) {
     OS << "  ";
     TypeObject.emitCxxEnumValue(OS);
     OS << ",\n";
   }
   OS << "};\n"
      << "const static LLT TypeObjects[] = {\n";
   for (const auto &TypeObject : TypeObjects) {
     OS << "  ";
     TypeObject.emitCxxConstructorCall(OS);
     OS << ",\n";
   }
   OS << "};\n\n";
 
   // Emit a table containing the PredicateBitsets objects needed by the matcher
   // and an enum for the matcher to reference them with.
   std::vector<std::vector<Record *>> FeatureBitsets;
   for (auto &Rule : Rules)
     FeatureBitsets.push_back(Rule.getRequiredFeatures());
-  std::sort(
+  llvm::sort(
       FeatureBitsets.begin(), FeatureBitsets.end(),
       [&](const std::vector<Record *> &A, const std::vector<Record *> &B) {
         if (A.size() < B.size())
           return true;
         if (A.size() > B.size())
           return false;
         for (const auto &Pair : zip(A, B)) {
           if (std::get<0>(Pair)->getName() < std::get<1>(Pair)->getName())

llvm/trunk/utils/TableGen/InfoByHwMode.cpp

void ValueTypeByHwMode::writeToStream(raw_ostream &OS) const {
   if (isSimple()) {
     OS << getMVTName(getSimple());
     return;
   }
 
   std::vector<const PairType*> Pairs;
   for (const auto &P : Map)
     Pairs.push_back(&P);
-  std::sort(Pairs.begin(), Pairs.end(), deref<std::less<PairType>>());
+  llvm::sort(Pairs.begin(), Pairs.end(), deref<std::less<PairType>>());
 
   OS << '{';
   for (unsigned i = 0, e = Pairs.size(); i != e; ++i) {
     const PairType *P = Pairs[i];
     OS << '(' << getModeName(P->first)
        << ':' << getMVTName(P->second).str() << ')';
     if (i != e-1)
       OS << ',';
return std::tie(A0.SpillSize, A0.SpillAlignment) >
          std::tie(B0.SpillSize, B0.SpillAlignment);
 }
 
 void RegSizeInfoByHwMode::writeToStream(raw_ostream &OS) const {
   typedef typename decltype(Map)::value_type PairType;
   std::vector<const PairType*> Pairs;
   for (const auto &P : Map)
     Pairs.push_back(&P);
-  std::sort(Pairs.begin(), Pairs.end(), deref<std::less<PairType>>());
+  llvm::sort(Pairs.begin(), Pairs.end(), deref<std::less<PairType>>());
 
   OS << '{';
   for (unsigned i = 0, e = Pairs.size(); i != e; ++i) {
     const PairType *P = Pairs[i];
     OS << '(' << getModeName(P->first) << ':' << P->second << ')';
     if (i != e-1)
       OS << ',';
   }

llvm/trunk/utils/TableGen/RegisterInfoEmitter.cpp

EmitRegUnitPressure(raw_ostream &OS, const CodeGenRegBank &RegBank,
 
   for (unsigned i = 0, e = NumRCUnitSets; i != e; ++i) {
     ArrayRef<unsigned> PSetIDs = RegBank.getRCPressureSetIDs(i);
     PSets[i].reserve(PSetIDs.size());
     for (ArrayRef<unsigned>::iterator PSetI = PSetIDs.begin(),
            PSetE = PSetIDs.end(); PSetI != PSetE; ++PSetI) {
       PSets[i].push_back(RegBank.getRegPressureSet(*PSetI).Order);
     }
-    std::sort(PSets[i].begin(), PSets[i].end());
+    llvm::sort(PSets[i].begin(), PSets[i].end());
     PSetsSeqs.add(PSets[i]);
   }
 
   PSetsSeqs.layout();
 
   OS << "/// Table of pressure sets per register class or unit.\n"
      << "static const int RCSetsTable[] = {\n";
   PSetsSeqs.emit(OS, printInt, "-1");

llvm/trunk/utils/TableGen/SubtargetEmitter.cpp

 
 //
 // Enumeration - Emit the specified class as an enumeration.
 //
 void SubtargetEmitter::Enumeration(raw_ostream &OS) {
   // Get all records of class and sort
   std::vector<Record*> DefList =
     Records.getAllDerivedDefinitions("SubtargetFeature");
-  std::sort(DefList.begin(), DefList.end(), LessRecord());
+  llvm::sort(DefList.begin(), DefList.end(), LessRecord());
 
   unsigned N = DefList.size();
   if (N == 0)
     return;
   if (N > MAX_SUBTARGET_FEATURES)
     PrintFatalError("Too many subtarget features! Bump MAX_SUBTARGET_FEATURES.");
 
   OS << "namespace " << Target << " {\n";

 unsigned SubtargetEmitter::FeatureKeyValues(raw_ostream &OS) {
   // Gather and sort all the features
   std::vector<Record*> FeatureList =
                            Records.getAllDerivedDefinitions("SubtargetFeature");
 
   if (FeatureList.empty())
     return 0;
 
-  std::sort(FeatureList.begin(), FeatureList.end(), LessRecordFieldName());
+  llvm::sort(FeatureList.begin(), FeatureList.end(), LessRecordFieldName());
 
   // Begin feature table
   OS << "// Sorted (by key) array of values for CPU features.\n"
      << "extern const llvm::SubtargetFeatureKV " << Target
      << "FeatureKV[] = {\n";
 
   // For each feature
   unsigned NumFeatures = 0;

 //
 // CPUKeyValues - Emit data of all the subtarget processors.  Used by command
 // line.
 //
 unsigned SubtargetEmitter::CPUKeyValues(raw_ostream &OS) {
   // Gather and sort processor information
   std::vector<Record*> ProcessorList =
                           Records.getAllDerivedDefinitions("Processor");
-  std::sort(ProcessorList.begin(), ProcessorList.end(), LessRecordFieldName());
+  llvm::sort(ProcessorList.begin(), ProcessorList.end(), LessRecordFieldName());
 
   // Begin processor table
   OS << "// Sorted (by key) array of values for CPU subtype.\n"
      << "extern const llvm::SubtargetFeatureKV " << Target
      << "SubTypeKV[] = {\n";
 
   // For each processor
   for (Record *Processor : ProcessorList) {
for (unsigned UseIdx = 0, EndIdx = Reads.size();
       IdxVec WriteIDs;
       if (ValidWrites.empty())
         WriteIDs.push_back(0);
       else {
         for (Record *VW : ValidWrites) {
           WriteIDs.push_back(SchedModels.getSchedRWIdx(VW, /*IsRead=*/false));
         }
       }
-      std::sort(WriteIDs.begin(), WriteIDs.end());
+      llvm::sort(WriteIDs.begin(), WriteIDs.end());
       for(unsigned W : WriteIDs) {
         MCReadAdvanceEntry RAEntry;
         RAEntry.UseIdx = UseIdx;
         RAEntry.WriteResourceID = W;
         RAEntry.Cycles = ReadAdvance->getValueAsInt("Cycles");
         ReadAdvanceEntries.push_back(RAEntry);
       }
     }
     if (SCDesc.NumMicroOps == MCSchedClassDesc::InvalidNumMicroOps) {
       WriteProcResources.clear();
       WriteLatencies.clear();
       ReadAdvanceEntries.clear();
     }
     // Add the information for this SchedClass to the global tables using basic
     // compression.
     //
     // WritePrecRes entries are sorted by ProcResIdx.
-    std::sort(WriteProcResources.begin(), WriteProcResources.end(),
+    llvm::sort(WriteProcResources.begin(), WriteProcResources.end(),
                LessWriteProcResources());
 
     SCDesc.NumWriteProcResEntries = WriteProcResources.size();
     std::vector<MCWriteProcResEntry>::iterator WPRPos =
       std::search(SchedTables.WriteProcResources.begin(),
                   SchedTables.WriteProcResources.end(),
                   WriteProcResources.begin(), WriteProcResources.end());
     if (WPRPos != SchedTables.WriteProcResources.end())
       SCDesc.WriteProcResIdx = WPRPos - SchedTables.WriteProcResources.begin();

 
 //
 // EmitProcessorLookup - generate cpu name to itinerary lookup table.
 //
 void SubtargetEmitter::EmitProcessorLookup(raw_ostream &OS) {
   // Gather and sort processor information
   std::vector<Record*> ProcessorList =
                           Records.getAllDerivedDefinitions("Processor");
-  std::sort(ProcessorList.begin(), ProcessorList.end(), LessRecordFieldName());
+  llvm::sort(ProcessorList.begin(), ProcessorList.end(), LessRecordFieldName());
 
   // Begin processor table
   OS << "\n";
   OS << "// Sorted (by key) array of itineraries for CPU subtype.\n"
      << "extern const llvm::SubtargetInfoKV "
      << Target << "ProcSchedKV[] = {\n";
 
   // For each processor

 
 void SubtargetEmitter::EmitSchedModelHelpers(const std::string &ClassName,
                                              raw_ostream &OS) {
   OS << "unsigned " << ClassName
      << "\n::resolveSchedClass(unsigned SchedClass, const MachineInstr *MI,"
      << " const TargetSchedModel *SchedModel) const {\n";
 
   std::vector<Record*> Prologs = Records.getAllDerivedDefinitions("PredicateProlog");
-  std::sort(Prologs.begin(), Prologs.end(), LessRecord());
+  llvm::sort(Prologs.begin(), Prologs.end(), LessRecord());
   for (Record *P : Prologs) {
     OS << P->getValueAsString("Code") << '\n';
   }
   IdxVec VariantClasses;
   for (const CodeGenSchedClass &SC : SchedModels.schedClasses()) {
     if (SC.Transitions.empty())
       continue;
     VariantClasses.push_back(SC.Index);

 // ParseFeaturesFunction - Produces a subtarget specific function for parsing
 // the subtarget features string.
 //
 void SubtargetEmitter::ParseFeaturesFunction(raw_ostream &OS,
                                              unsigned NumFeatures,
                                              unsigned NumProcs) {
   std::vector<Record*> Features =
                        Records.getAllDerivedDefinitions("SubtargetFeature");
-  std::sort(Features.begin(), Features.end(), LessRecord());
+  llvm::sort(Features.begin(), Features.end(), LessRecord());
 
   OS << "// ParseSubtargetFeatures - Parses features string setting specified\n"
      << "// subtarget options.\n"
      << "void llvm::";
   OS << Target;
   OS << "Subtarget::ParseSubtargetFeatures(StringRef CPU, StringRef FS) {\n"
      << "  DEBUG(dbgs() << \"\\nFeatures:\" << FS);\n"
      << "  DEBUG(dbgs() << \"\\nCPU:\" << CPU << \"\\n\\n\");\n";