[include] 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.

[echristo]

As the general idea was already approved, LGTM.

llvm/trunk/include/llvm/Analysis/LoopInfoImpl.h

for (DenseMap<BasicBlock*, LoopT*>::const_iterator I = BBMap.begin(),
          E = BBMap.end(); I != E; ++I)
     OS << "BB '" << I->first->getName() << "' level = "
        << I->second->getLoopDepth() << "\n";
 #endif
 }
 
 template <typename T>
 bool compareVectors(std::vector<T> &BB1, std::vector<T> &BB2) {
-  std::sort(BB1.begin(), BB1.end());
-  std::sort(BB2.begin(), BB2.end());
+  llvm::sort(BB1.begin(), BB1.end());
+  llvm::sort(BB2.begin(), BB2.end());
   return BB1 == BB2;
 }
 
 template <class BlockT, class LoopT>
 void addInnerLoopsToHeadersMap(DenseMap<BlockT *, const LoopT *> &LoopHeaders,
                                const LoopInfoBase<BlockT, LoopT> &LI,
                                const LoopT &L) {
   LoopHeaders[L.getHeader()] = &L;

llvm/trunk/include/llvm/CodeGen/SlotIndexes.h

void insertMBBInMaps(MachineBasicBlock *mbb) {
       MBBRanges[prevMBB->getNumber()].second = startIdx;
 
       assert(unsigned(mbb->getNumber()) == MBBRanges.size() &&
              "Blocks must be added in order");
       MBBRanges.push_back(std::make_pair(startIdx, endIdx));
       idx2MBBMap.push_back(IdxMBBPair(startIdx, mbb));
 
       renumberIndexes(newItr);
-      std::sort(idx2MBBMap.begin(), idx2MBBMap.end(), Idx2MBBCompare());
+      llvm::sort(idx2MBBMap.begin(), idx2MBBMap.end(), Idx2MBBCompare());
     }
 
     /// \brief Free the resources that were required to maintain a SlotIndex.
     ///
     /// Once an index is no longer needed (for instance because the instruction
     /// at that index has been moved), the resources required to maintain the
     /// index can be relinquished to reduce memory use and improve renumbering
     /// performance. Any remaining SlotIndex objects that point to the same

llvm/trunk/include/llvm/ProfileData/InstrProf.h

Error InstrProfSymtab::create(const NameIterRange &IterRange) {
 
   finalizeSymtab();
   return Error::success();
 }
 
 void InstrProfSymtab::finalizeSymtab() {
   if (Sorted)
     return;
-  std::sort(MD5NameMap.begin(), MD5NameMap.end(), less_first());
-  std::sort(MD5FuncMap.begin(), MD5FuncMap.end(), less_first());
-  std::sort(AddrToMD5Map.begin(), AddrToMD5Map.end(), less_first());
+  llvm::sort(MD5NameMap.begin(), MD5NameMap.end(), less_first());
+  llvm::sort(MD5FuncMap.begin(), MD5FuncMap.end(), less_first());
+  llvm::sort(AddrToMD5Map.begin(), AddrToMD5Map.end(), less_first());
   AddrToMD5Map.erase(std::unique(AddrToMD5Map.begin(), AddrToMD5Map.end()),
                      AddrToMD5Map.end());
   Sorted = true;
 }
 
 StringRef InstrProfSymtab::getFuncNameOrExternalSymbol(uint64_t FuncMD5Hash) {
   StringRef ret = getFuncName(FuncMD5Hash);
   if (ret.empty())

llvm/trunk/include/llvm/Support/GenericDomTreeConstruction.h

static void LegalizeUpdates(ArrayRef<UpdateT> AllUpdates,
     for (size_t i = 0, e = AllUpdates.size(); i != e; ++i) {
       const auto &U = AllUpdates[i];
       if (!IsPostDom)
         Operations[{U.getFrom(), U.getTo()}] = int(i);
       else
         Operations[{U.getTo(), U.getFrom()}] = int(i);
     }
 
-    std::sort(Result.begin(), Result.end(),
+    llvm::sort(Result.begin(), Result.end(),
                [&Operations](const UpdateT &A, const UpdateT &B) {
                  return Operations[{A.getFrom(), A.getTo()}] >
                         Operations[{B.getFrom(), B.getTo()}];
                });
   }
 
   static void ApplyNextUpdate(DomTreeT &DT, BatchUpdateInfo &BUI) {
     assert(!BUI.Updates.empty() && "No updates to apply!");
     UpdateT CurrentUpdate = BUI.Updates.pop_back_val();
     DEBUG(dbgs() << "Applying update: " << CurrentUpdate << "\n");
 
     // Move to the next snapshot of the CFG by removing the reverse-applied
for (const auto &NodeToTN : DT.DomTreeNodes) {
         }
 
         continue;
       }
 
       // Make a copy and sort it such that it is possible to check if there are
       // no gaps between DFS numbers of adjacent children.
       SmallVector<TreeNodePtr, 8> Children(Node->begin(), Node->end());
-      std::sort(Children.begin(), Children.end(),
+      llvm::sort(Children.begin(), Children.end(),
                  [](const TreeNodePtr Ch1, const TreeNodePtr Ch2) {
                    return Ch1->getDFSNumIn() < Ch2->getDFSNumIn();
                  });
 
       auto PrintChildrenError = [Node, &Children, PrintNodeAndDFSNums](
           const TreeNodePtr FirstCh, const TreeNodePtr SecondCh) {
         assert(FirstCh);
 
         errs() << "Incorrect DFS numbers for:\n\tParent ";
         PrintNodeAndDFSNums(Node);
 

llvm/trunk/include/llvm/Support/Parallel.h

return Comp(*Start, *(End - 1))
                                    : Start);
 }
 
 template <class RandomAccessIterator, class Comparator>
 void parallel_quick_sort(RandomAccessIterator Start, RandomAccessIterator End,
                          const Comparator &Comp, TaskGroup &TG, size_t Depth) {
   // Do a sequential sort for small inputs.
   if (std::distance(Start, End) < detail::MinParallelSize || Depth == 0) {
-    std::sort(Start, End, Comp);
+    llvm::sort(Start, End, Comp);
     return;
   }
 
   // Partition.
   auto Pivot = medianOf3(Start, End, Comp);
   // Move Pivot to End.
   std::swap(*(End - 1), *Pivot);
   Pivot = std::partition(Start, End - 1, [&Comp, End](decltype(*Start) V) {

 
 // sequential algorithm implementations.
 template <class Policy, class RandomAccessIterator,
           class Comparator = detail::DefComparator<RandomAccessIterator>>
 void sort(Policy policy, RandomAccessIterator Start, RandomAccessIterator End,
           const Comparator &Comp = Comparator()) {
   static_assert(is_execution_policy<Policy>::value,
                 "Invalid execution policy!");
-  std::sort(Start, End, Comp);
+  llvm::sort(Start, End, Comp);
 }
 
 template <class Policy, class IterTy, class FuncTy>
 void for_each(Policy policy, IterTy Begin, IterTy End, FuncTy Fn) {
   static_assert(is_execution_policy<Policy>::value,
                 "Invalid execution policy!");
   std::for_each(Begin, End, Fn);
 }

llvm/trunk/include/llvm/Support/ScopedPrinter.h

for (const auto &Flag : Flags) {
         EnumMask = EnumMask3;
       bool IsEnum = (Flag.Value & EnumMask) != 0;
       if ((!IsEnum && (Value & Flag.Value) == Flag.Value) ||
           (IsEnum && (Value & EnumMask) == Flag.Value)) {
         SetFlags.push_back(Flag);
       }
     }
 
-    std::sort(SetFlags.begin(), SetFlags.end(), &flagName<TFlag>);
+    llvm::sort(SetFlags.begin(), SetFlags.end(), &flagName<TFlag>);
 
     startLine() << Label << " [ (" << hex(Value) << ")\n";
     for (const auto &Flag : SetFlags) {
       startLine() << "  " << Flag.Name << " (" << hex(Flag.Value) << ")\n";
     }
     startLine() << "]\n";
   }