[Analysis] 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 D44363 for a list of all the required patches.

[dexonsmith]

LGTM.

llvm/trunk/lib/Analysis/BlockFrequencyInfoImpl.cpp

if (W.Amount > W.Amount + OtherW.Amount)
     // Saturate on overflow.
     W.Amount = UINT64_MAX;
   else
     W.Amount += OtherW.Amount;
 }
 
 static void combineWeightsBySorting(WeightList &Weights) {
   // Sort so edges to the same node are adjacent.
-  std::sort(Weights.begin(), Weights.end(),
+  llvm::sort(Weights.begin(), Weights.end(),
              [](const Weight &L,
                 const Weight &R) { return L.TargetNode < R.TargetNode; });
 
   // Combine adjacent edges.
   WeightList::iterator O = Weights.begin();
   for (WeightList::const_iterator I = O, L = O, E = Weights.end(); I != E;
        ++O, (I = L)) {
     *O = *I;
 
     // Find the adjacent weights to the same node.
for (const auto *P : make_range(Irr.pred_begin(), Irr.pred_end())) {
       DEBUG(dbgs() << "  => entry = " << BFI.getBlockName(Irr.Node) << "\n");
       break;
     }
   }
   assert(Headers.size() >= 2 &&
          "Expected irreducible CFG; -loop-info is likely invalid");
   if (Headers.size() == InSCC.size()) {
     // Every block is a header.
-    std::sort(Headers.begin(), Headers.end());
+    llvm::sort(Headers.begin(), Headers.end());
     return;
   }
 
   // Look for extra headers from irreducible sub-SCCs.
   for (const auto &I : InSCC) {
     // Entry blocks are already headers.
     if (I.second)
       continue;
for (const auto &I : InSCC) {
     if (Headers.back() == Irr.Node)
       // Added this as a header.
       continue;
 
     // This is not a header.
     Others.push_back(Irr.Node);
     DEBUG(dbgs() << "  => other = " << BFI.getBlockName(Irr.Node) << "\n");
   }
-  std::sort(Headers.begin(), Headers.end());
-  std::sort(Others.begin(), Others.end());
+  llvm::sort(Headers.begin(), Headers.end());
+  llvm::sort(Others.begin(), Others.end());
 }
 
 static void createIrreducibleLoop(
     BlockFrequencyInfoImplBase &BFI, const IrreducibleGraph &G,
     LoopData *OuterLoop, std::list<LoopData>::iterator Insert,
     const std::vector<const IrreducibleGraph::IrrNode *> &SCC) {
   // Translate the SCC into RPO.
   DEBUG(dbgs() << " - found-scc\n");

llvm/trunk/lib/Analysis/CFLAndersAliasAnalysis.cpp

for (const auto &OuterMapping : ReachSet.value_mappings()) {
     auto &AliasList = AliasMap[Val];
     for (const auto &InnerMapping : OuterMapping.second) {
       // Again, AliasMap only cares about top-level values
       if (InnerMapping.first.DerefLevel == 0)
         AliasList.push_back(OffsetValue{InnerMapping.first.Val, UnknownOffset});
     }
 
     // Sort AliasList for faster lookup
-    std::sort(AliasList.begin(), AliasList.end());
+    llvm::sort(AliasList.begin(), AliasList.end());
   }
 }
 
 static void populateExternalRelations(
     SmallVectorImpl<ExternalRelation> &ExtRelations, const Function &Fn,
     const SmallVectorImpl<Value *> &RetVals, const ReachabilitySet &ReachSet) {
   // If a function only returns one of its argument X, then X will be both an
   // argument and a return value at the same time. This is an edge case that
for (const auto &FromRecord : Mapping.second.FromRecords) {
         ExtRelations.push_back(ExternalRelation{
             InterfaceValue{SrcIndex, SrcLevel},
             InterfaceValue{DstIndex, DstLevel}, UnknownOffset});
       }
     }
   }
 
   // Remove duplicates in ExtRelations
-  std::sort(ExtRelations.begin(), ExtRelations.end());
+  llvm::sort(ExtRelations.begin(), ExtRelations.end());
   ExtRelations.erase(std::unique(ExtRelations.begin(), ExtRelations.end()),
                      ExtRelations.end());
 }
 
 static void populateExternalAttributes(
     SmallVectorImpl<ExternalAttribute> &ExtAttributes, const Function &Fn,
     const SmallVectorImpl<Value *> &RetVals, const AliasAttrMap &AMap) {
   for (const auto &Mapping : AMap.mappings()) {

llvm/trunk/lib/Analysis/CallGraph.cpp

void CallGraph::print(raw_ostream &OS) const {
   // this here to avoid slowing down the non-printing fast path.
 
   SmallVector<CallGraphNode *, 16> Nodes;
   Nodes.reserve(FunctionMap.size());
 
   for (const auto &I : *this)
     Nodes.push_back(I.second.get());
 
-  std::sort(Nodes.begin(), Nodes.end(),
+  llvm::sort(Nodes.begin(), Nodes.end(),
              [](CallGraphNode *LHS, CallGraphNode *RHS) {
     if (Function *LF = LHS->getFunction())
       if (Function *RF = RHS->getFunction())
         return LF->getName() < RF->getName();
 
     return RHS->getFunction() != nullptr;
   });
 
   for (CallGraphNode *CN : Nodes)

llvm/trunk/lib/Analysis/MemoryDependenceAnalysis.cpp

if (!Cache.empty()) {
 
     // If we already have a partially computed set of results, scan them to
     // determine what is dirty, seeding our initial DirtyBlocks worklist.
     for (auto &Entry : Cache)
       if (Entry.getResult().isDirty())
         DirtyBlocks.push_back(Entry.getBB());
 
     // Sort the cache so that we can do fast binary search lookups below.
-    std::sort(Cache.begin(), Cache.end());
+    llvm::sort(Cache.begin(), Cache.end());
 
     ++NumCacheDirtyNonLocal;
     // cerr << "CACHED CASE: " << DirtyBlocks.size() << " dirty: "
     //     << Cache.size() << " cached: " << *QueryInst;
   } else {
     // Seed DirtyBlocks with each of the preds of QueryInst's block.
     BasicBlock *QueryBB = QueryCS.getInstruction()->getParent();
     for (BasicBlock *Pred : PredCache.get(QueryBB))
if (Cache.size() != 1) {
       Cache.pop_back();
       MemoryDependenceResults::NonLocalDepInfo::iterator Entry =
           std::upper_bound(Cache.begin(), Cache.end(), Val);
       Cache.insert(Entry, Val);
     }
     break;
   default:
     // Added many values, do a full scale sort.
-    std::sort(Cache.begin(), Cache.end());
+    llvm::sort(Cache.begin(), Cache.end());
     break;
   }
 }
 
 /// Perform a dependency query based on pointer/pointeesize starting at the end
 /// of StartBB.
 ///
 /// Add any clobber/def results to the results vector and keep track of which
for (ValueIsLoadPair P : ReversePtrDepIt->second) {
         Entry.setResult(NewDirtyVal);
 
         if (Instruction *NewDirtyInst = NewDirtyVal.getInst())
           ReversePtrDepsToAdd.push_back(std::make_pair(NewDirtyInst, P));
       }
 
       // Re-sort the NonLocalDepInfo.  Changing the dirty entry to its
       // subsequent value may invalidate the sortedness.
-      std::sort(NLPDI.begin(), NLPDI.end());
+      llvm::sort(NLPDI.begin(), NLPDI.end());
     }
 
     ReverseNonLocalPtrDeps.erase(ReversePtrDepIt);
 
     while (!ReversePtrDepsToAdd.empty()) {
       ReverseNonLocalPtrDeps[ReversePtrDepsToAdd.back().first].insert(
           ReversePtrDepsToAdd.back().second);
       ReversePtrDepsToAdd.pop_back();

llvm/trunk/lib/Analysis/MemorySSA.cpp

void MemorySSA::placePHINodes(
     const SmallPtrSetImpl<BasicBlock *> &DefiningBlocks,
     const DenseMap<const BasicBlock *, unsigned int> &BBNumbers) {
   // Determine where our MemoryPhi's should go
   ForwardIDFCalculator IDFs(*DT);
   IDFs.setDefiningBlocks(DefiningBlocks);
   SmallVector<BasicBlock *, 32> IDFBlocks;
   IDFs.calculate(IDFBlocks);
 
-  std::sort(IDFBlocks.begin(), IDFBlocks.end(),
+  llvm::sort(IDFBlocks.begin(), IDFBlocks.end(),
              [&BBNumbers](const BasicBlock *A, const BasicBlock *B) {
                return BBNumbers.lookup(A) < BBNumbers.lookup(B);
              });
 
   // Now place MemoryPhi nodes.
   for (auto &BB : IDFBlocks)
     createMemoryPhi(BB);
 }
 
 void MemorySSA::buildMemorySSA() {
   // We create an access to represent "live on entry", for things like

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

DEBUG({
         dbgs() << *T << "\n";
     });
 
   // Remove duplicates.
   array_pod_sort(Terms.begin(), Terms.end());
   Terms.erase(std::unique(Terms.begin(), Terms.end()), Terms.end());
 
   // Put larger terms first.
-  std::sort(Terms.begin(), Terms.end(), [](const SCEV *LHS, const SCEV *RHS) {
+  llvm::sort(Terms.begin(), Terms.end(), [](const SCEV *LHS, const SCEV *RHS) {
     return numberOfTerms(LHS) > numberOfTerms(RHS);
   });
 
   // Try to divide all terms by the element size. If term is not divisible by
   // element size, proceed with the original term.
   for (const SCEV *&Term : Terms) {
     const SCEV *Q, *R;
     SCEVDivision::divide(*this, Term, ElementSize, &Q, &R);

llvm/trunk/lib/Analysis/ScalarEvolutionExpander.cpp

SCEVExpander::replaceCongruentIVs(Loop *L, const DominatorTree *DT,
                                   SmallVectorImpl<WeakTrackingVH> &DeadInsts,
                                   const TargetTransformInfo *TTI) {
   // Find integer phis in order of increasing width.
   SmallVector<PHINode*, 8> Phis;
   for (PHINode &PN : L->getHeader()->phis())
     Phis.push_back(&PN);
 
   if (TTI)
-    std::sort(Phis.begin(), Phis.end(), [](Value *LHS, Value *RHS) {
+    llvm::sort(Phis.begin(), Phis.end(), [](Value *LHS, Value *RHS) {
       // Put pointers at the back and make sure pointer < pointer = false.
       if (!LHS->getType()->isIntegerTy() || !RHS->getType()->isIntegerTy())
         return RHS->getType()->isIntegerTy() && !LHS->getType()->isIntegerTy();
       return RHS->getType()->getPrimitiveSizeInBits() <
              LHS->getType()->getPrimitiveSizeInBits();
     });
 
   unsigned NumElim = 0;

llvm/trunk/lib/Analysis/TargetLibraryInfo.cpp

 }
 
 static bool compareWithVectorFnName(const VecDesc &LHS, StringRef S) {
   return LHS.VectorFnName < S;
 }
 
 void TargetLibraryInfoImpl::addVectorizableFunctions(ArrayRef<VecDesc> Fns) {
   VectorDescs.insert(VectorDescs.end(), Fns.begin(), Fns.end());
-  std::sort(VectorDescs.begin(), VectorDescs.end(), compareByScalarFnName);
+  llvm::sort(VectorDescs.begin(), VectorDescs.end(), compareByScalarFnName);
 
   ScalarDescs.insert(ScalarDescs.end(), Fns.begin(), Fns.end());
-  std::sort(ScalarDescs.begin(), ScalarDescs.end(), compareByVectorFnName);
+  llvm::sort(ScalarDescs.begin(), ScalarDescs.end(), compareByVectorFnName);
 }
 
 void TargetLibraryInfoImpl::addVectorizableFunctionsFromVecLib(
     enum VectorLibrary VecLib) {
   switch (VecLib) {
   case Accelerate: {
     const VecDesc VecFuncs[] = {
         // Floating-Point Arithmetic and Auxiliary Functions