[Analysis] Change std::sort to llvm::sort in response to r327219
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.
Reviewers: sanjoy, dexonsmith, hfinkel, RKSimon
Reviewed By: dexonsmith
Subscribers: david2050, llvm-commits
Differential Revision: https://reviews.llvm.org/D44944
llvm-svn: 328925
diff --git a/llvm/lib/Analysis/BlockFrequencyInfoImpl.cpp b/llvm/lib/Analysis/BlockFrequencyInfoImpl.cpp
index c9d27a2..5369d9f 100644
--- a/llvm/lib/Analysis/BlockFrequencyInfoImpl.cpp
+++ b/llvm/lib/Analysis/BlockFrequencyInfoImpl.cpp
@@ -155,9 +155,9 @@
static void combineWeightsBySorting(WeightList &Weights) {
// Sort so edges to the same node are adjacent.
- std::sort(Weights.begin(), Weights.end(),
- [](const Weight &L,
- const Weight &R) { return L.TargetNode < R.TargetNode; });
+ 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();
@@ -702,7 +702,7 @@
"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;
}
@@ -736,8 +736,8 @@
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(
diff --git a/llvm/lib/Analysis/CFLAndersAliasAnalysis.cpp b/llvm/lib/Analysis/CFLAndersAliasAnalysis.cpp
index 7138f18..cdb7ca9 100644
--- a/llvm/lib/Analysis/CFLAndersAliasAnalysis.cpp
+++ b/llvm/lib/Analysis/CFLAndersAliasAnalysis.cpp
@@ -395,7 +395,7 @@
}
// Sort AliasList for faster lookup
- std::sort(AliasList.begin(), AliasList.end());
+ llvm::sort(AliasList.begin(), AliasList.end());
}
}
@@ -479,7 +479,7 @@
}
// 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());
}
diff --git a/llvm/lib/Analysis/CallGraph.cpp b/llvm/lib/Analysis/CallGraph.cpp
index ac3ea2b..ad410a3 100644
--- a/llvm/lib/Analysis/CallGraph.cpp
+++ b/llvm/lib/Analysis/CallGraph.cpp
@@ -96,8 +96,8 @@
for (const auto &I : *this)
Nodes.push_back(I.second.get());
- std::sort(Nodes.begin(), Nodes.end(),
- [](CallGraphNode *LHS, CallGraphNode *RHS) {
+ 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();
diff --git a/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp b/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp
index 0514426..9b080e1 100644
--- a/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp
+++ b/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp
@@ -805,7 +805,7 @@
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: "
@@ -1068,7 +1068,7 @@
break;
default:
// Added many values, do a full scale sort.
- std::sort(Cache.begin(), Cache.end());
+ llvm::sort(Cache.begin(), Cache.end());
break;
}
}
@@ -1638,7 +1638,7 @@
// 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);
diff --git a/llvm/lib/Analysis/MemorySSA.cpp b/llvm/lib/Analysis/MemorySSA.cpp
index c8fef6a..e1a15e1 100644
--- a/llvm/lib/Analysis/MemorySSA.cpp
+++ b/llvm/lib/Analysis/MemorySSA.cpp
@@ -1338,10 +1338,10 @@
SmallVector<BasicBlock *, 32> IDFBlocks;
IDFs.calculate(IDFBlocks);
- std::sort(IDFBlocks.begin(), IDFBlocks.end(),
- [&BBNumbers](const BasicBlock *A, const BasicBlock *B) {
- return BBNumbers.lookup(A) < BBNumbers.lookup(B);
- });
+ 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)
diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp
index a767597..a6b3dce 100644
--- a/llvm/lib/Analysis/ScalarEvolution.cpp
+++ b/llvm/lib/Analysis/ScalarEvolution.cpp
@@ -10645,7 +10645,7 @@
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);
});
diff --git a/llvm/lib/Analysis/ScalarEvolutionExpander.cpp b/llvm/lib/Analysis/ScalarEvolutionExpander.cpp
index 78a22e3..e2113d1 100644
--- a/llvm/lib/Analysis/ScalarEvolutionExpander.cpp
+++ b/llvm/lib/Analysis/ScalarEvolutionExpander.cpp
@@ -1862,7 +1862,7 @@
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();
diff --git a/llvm/lib/Analysis/TargetLibraryInfo.cpp b/llvm/lib/Analysis/TargetLibraryInfo.cpp
index 87b4051..c605c91 100644
--- a/llvm/lib/Analysis/TargetLibraryInfo.cpp
+++ b/llvm/lib/Analysis/TargetLibraryInfo.cpp
@@ -1329,10 +1329,10 @@
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(