Use llvm::stable_sort

Make some small adjustment while touching the code: make parameters
const, use less_first(), etc.

Differential Revision: https://reviews.llvm.org/D60989

llvm-svn: 358943

13 files changed, 60 insertions, 72 deletions

diff --git a/lld/COFF/ICF.cpp b/lld/COFF/ICF.cpp
index 0d204f62afa..7480bfe8623 100644
--- a/lld/COFF/ICF.cpp
+++ b/lld/COFF/ICF.cpp
@@ -279,10 +279,9 @@ void ICF::run(ArrayRef<Chunk *> Vec) {
 
   // From now on, sections in Chunks are ordered so that sections in
   // the same group are consecutive in the vector.
-  std::stable_sort(Chunks.begin(), Chunks.end(),
-                   [](SectionChunk *A, SectionChunk *B) {
-                     return A->Class[0] < B->Class[0];
-                   });
+  llvm::stable_sort(Chunks, [](const SectionChunk *A, const SectionChunk *B) {
+    return A->Class[0] < B->Class[0];
+  });
 
   // Compare static contents and assign unique IDs for each static content.
   forEachClass([&](size_t Begin, size_t End) { segregate(Begin, End, true); });
diff --git a/lld/COFF/Writer.cpp b/lld/COFF/Writer.cpp
index 0419cef5ea6..ff1363e7b13 100644
--- a/lld/COFF/Writer.cpp
+++ b/lld/COFF/Writer.cpp
@@ -642,10 +642,9 @@ static void sortBySectionOrder(std::vector<Chunk *> &Chunks) {
     return 0;
   };
 
-  std::stable_sort(Chunks.begin(), Chunks.end(),
-                   [=](const Chunk *A, const Chunk *B) {
-                     return GetPriority(A) < GetPriority(B);
-                   });
+  llvm::stable_sort(Chunks, [=](const Chunk *A, const Chunk *B) {
+    return GetPriority(A) < GetPriority(B);
+  });
 }
 
 // Sort concrete section chunks from GNU import libraries.
@@ -683,10 +682,9 @@ bool Writer::fixGnuImportChunks() {
     if (!PSec->Name.startswith(".idata"))
       continue;
 
-    std::vector<Chunk *> &Chunks = PSec->Chunks;
-    if (!Chunks.empty())
+    if (!PSec->Chunks.empty())
       HasIdata = true;
-    std::stable_sort(Chunks.begin(), Chunks.end(), [&](Chunk *S, Chunk *T) {
+    llvm::stable_sort(PSec->Chunks, [&](Chunk *S, Chunk *T) {
       SectionChunk *SC1 = dyn_cast_or_null<SectionChunk>(S);
       SectionChunk *SC2 = dyn_cast_or_null<SectionChunk>(T);
       if (!SC1 || !SC2) {
@@ -845,7 +843,7 @@ void Writer::createSections() {
   }
 
   // Finally, move some output sections to the end.
-  auto SectionOrder = [&](OutputSection *S) {
+  auto SectionOrder = [&](const OutputSection *S) {
     // Move DISCARDABLE (or non-memory-mapped) sections to the end of file because
     // the loader cannot handle holes. Stripping can remove other discardable ones
     // than .reloc, which is first of them (created early).
@@ -858,10 +856,10 @@ void Writer::createSections() {
       return 1;
     return 0;
   };
-  std::stable_sort(OutputSections.begin(), OutputSections.end(),
-                   [&](OutputSection *S, OutputSection *T) {
-                     return SectionOrder(S) < SectionOrder(T);
-                   });
+  llvm::stable_sort(OutputSections,
+                    [&](const OutputSection *S, const OutputSection *T) {
+                      return SectionOrder(S) < SectionOrder(T);
+                    });
 }
 
 void Writer::createMiscChunks() {
@@ -1779,7 +1777,7 @@ void Writer::sortCRTSectionChunks(std::vector<Chunk *> &Chunks) {
 
     return SAObj == SBObj && SA->getSectionNumber() < SB->getSectionNumber();
   };
-  std::stable_sort(Chunks.begin(), Chunks.end(), SectionChunkOrder);
+  llvm::stable_sort(Chunks, SectionChunkOrder);
 
   if (Config->Verbose) {
     for (auto &C : Chunks) {
diff --git a/lld/ELF/AArch64ErrataFix.cpp b/lld/ELF/AArch64ErrataFix.cpp
index 78e8d2912c5..ebf43ea5095 100644
--- a/lld/ELF/AArch64ErrataFix.cpp
+++ b/lld/ELF/AArch64ErrataFix.cpp
@@ -463,9 +463,9 @@ void AArch64Err843419Patcher::init() {
     std::vector<const Defined *> &MapSyms = KV.second;
     if (MapSyms.size() <= 1)
       continue;
-    std::stable_sort(
-        MapSyms.begin(), MapSyms.end(),
-        [](const Defined *A, const Defined *B) { return A->Value < B->Value; });
+    llvm::stable_sort(MapSyms, [](const Defined *A, const Defined *B) {
+      return A->Value < B->Value;
+    });
     MapSyms.erase(
         std::unique(MapSyms.begin(), MapSyms.end(),
                     [=](const Defined *A, const Defined *B) {
diff --git a/lld/ELF/CallGraphSort.cpp b/lld/ELF/CallGraphSort.cpp
index 10fc6bf4416..eacaca72d8d 100644
--- a/lld/ELF/CallGraphSort.cpp
+++ b/lld/ELF/CallGraphSort.cpp
@@ -172,8 +172,8 @@ void CallGraphSort::groupClusters() {
     SecToCluster[I] = &Clusters[I];
   }
 
-  std::stable_sort(SortedSecs.begin(), SortedSecs.end(), [&](int A, int B) {
-    return Clusters[B].getDensity() < Clusters[A].getDensity();
+  llvm::stable_sort(SortedSecs, [&](int A, int B) {
+    return Clusters[A].getDensity() > Clusters[B].getDensity();
   });
 
   for (int SI : SortedSecs) {
@@ -209,10 +209,9 @@ void CallGraphSort::groupClusters() {
   });
 
   // Sort by density.
-  std::stable_sort(Clusters.begin(), Clusters.end(),
-                   [](const Cluster &A, const Cluster &B) {
-                     return A.getDensity() > B.getDensity();
-                   });
+  llvm::stable_sort(Clusters, [](const Cluster &A, const Cluster &B) {
+    return A.getDensity() > B.getDensity();
+  });
 }
 
 DenseMap<const InputSectionBase *, int> CallGraphSort::run() {
diff --git a/lld/ELF/ICF.cpp b/lld/ELF/ICF.cpp
index 7c07a42a8a9..546b1214ec7 100644
--- a/lld/ELF/ICF.cpp
+++ b/lld/ELF/ICF.cpp
@@ -467,10 +467,9 @@ template <class ELFT> void ICF<ELFT>::run() {
 
   // From now on, sections in Sections vector are ordered so that sections
   // in the same equivalence class are consecutive in the vector.
-  std::stable_sort(Sections.begin(), Sections.end(),
-                   [](InputSection *A, InputSection *B) {
-                     return A->Class[0] < B->Class[0];
-                   });
+  llvm::stable_sort(Sections, [](const InputSection *A, const InputSection *B) {
+    return A->Class[0] < B->Class[0];
+  });
 
   // Compare static contents and assign unique IDs for each static content.
   forEachClass([&](size_t Begin, size_t End) { segregate(Begin, End, true); });
diff --git a/lld/ELF/LinkerScript.cpp b/lld/ELF/LinkerScript.cpp
index c06c3bd9acb..d6e7a28cdca 100644
--- a/lld/ELF/LinkerScript.cpp
+++ b/lld/ELF/LinkerScript.cpp
@@ -345,7 +345,7 @@ static bool matchConstraints(ArrayRef<InputSection *> Sections,
 static void sortSections(MutableArrayRef<InputSection *> Vec,
                          SortSectionPolicy K) {
   if (K != SortSectionPolicy::Default && K != SortSectionPolicy::None)
-    std::stable_sort(Vec.begin(), Vec.end(), getComparator(K));
+    llvm::stable_sort(Vec, getComparator(K));
 }
 
 // Sort sections as instructed by SORT-family commands and --sort-section
diff --git a/lld/ELF/MapFile.cpp b/lld/ELF/MapFile.cpp
index d9ff3e7382d..11720e196d3 100644
--- a/lld/ELF/MapFile.cpp
+++ b/lld/ELF/MapFile.cpp
@@ -72,12 +72,10 @@ static SymbolMapTy getSectionSyms(ArrayRef<Defined *> Syms) {
   // Sort symbols by address. We want to print out symbols in the
   // order in the output file rather than the order they appeared
   // in the input files.
-  for (auto &It : Ret) {
-    SmallVectorImpl<Defined *> &V = It.second;
-    std::stable_sort(V.begin(), V.end(), [](Defined *A, Defined *B) {
+  for (auto &It : Ret)
+    llvm::stable_sort(It.second, [](Defined *A, Defined *B) {
       return A->getVA() < B->getVA();
     });
-  }
   return Ret;
 }
 
diff --git a/lld/ELF/OutputSections.cpp b/lld/ELF/OutputSections.cpp
index 6a80b5b104f..6919ec465a0 100644
--- a/lld/ELF/OutputSections.cpp
+++ b/lld/ELF/OutputSections.cpp
@@ -138,13 +138,10 @@ void OutputSection::addSection(InputSection *IS) {
 
 static void sortByOrder(MutableArrayRef<InputSection *> In,
                         llvm::function_ref<int(InputSectionBase *S)> Order) {
-  using Pair = std::pair<int, InputSection *>;
-  auto Comp = [](const Pair &A, const Pair &B) { return A.first < B.first; };
-
-  std::vector<Pair> V;
+  std::vector<std::pair<int, InputSection *>> V;
   for (InputSection *S : In)
     V.push_back({Order(S), S});
-  std::stable_sort(V.begin(), V.end(), Comp);
+  llvm::stable_sort(V, less_first());
 
   for (size_t I = 0; I < V.size(); ++I)
     In[I] = V[I].second;
@@ -369,7 +366,7 @@ static bool compCtors(const InputSection *A, const InputSection *B) {
 void OutputSection::sortCtorsDtors() {
   assert(SectionCommands.size() == 1);
   auto *ISD = cast<InputSectionDescription>(SectionCommands[0]);
-  std::stable_sort(ISD->Sections.begin(), ISD->Sections.end(), compCtors);
+  llvm::stable_sort(ISD->Sections, compCtors);
 }
 
 // If an input string is in the form of "foo.N" where N is a number,
diff --git a/lld/ELF/Relocations.cpp b/lld/ELF/Relocations.cpp
index d5c36b667f7..2fe44fc6303 100644
--- a/lld/ELF/Relocations.cpp
+++ b/lld/ELF/Relocations.cpp
@@ -1243,10 +1243,10 @@ static void scanRelocs(InputSectionBase &Sec, ArrayRef<RelTy> Rels) {
 
   // Sort relocations by offset to binary search for R_RISCV_PCREL_HI20
   if (Config->EMachine == EM_RISCV)
-    std::stable_sort(Sec.Relocations.begin(), Sec.Relocations.end(),
-                     [](const Relocation &LHS, const Relocation &RHS) {
-                       return LHS.Offset < RHS.Offset;
-                     });
+    llvm::stable_sort(Sec.Relocations,
+                      [](const Relocation &LHS, const Relocation &RHS) {
+                        return LHS.Offset < RHS.Offset;
+                      });
 }
 
 template <class ELFT> void elf::scanRelocations(InputSectionBase &S) {
@@ -1418,10 +1418,10 @@ void ThunkCreator::mergeThunks(ArrayRef<OutputSection *> OutputSections) {
         for (const std::pair<ThunkSection *, uint32_t> TS : ISD->ThunkSections)
           if (TS.second == Pass)
             NewThunks.push_back(TS.first);
-        std::stable_sort(NewThunks.begin(), NewThunks.end(),
-                         [](const ThunkSection *A, const ThunkSection *B) {
-                           return A->OutSecOff < B->OutSecOff;
-                         });
+        llvm::stable_sort(NewThunks,
+                          [](const ThunkSection *A, const ThunkSection *B) {
+                            return A->OutSecOff < B->OutSecOff;
+                          });
 
         // Merge sorted vectors of Thunks and InputSections by OutSecOff
         std::vector<InputSection *> Tmp;
diff --git a/lld/ELF/SyntheticSections.cpp b/lld/ELF/SyntheticSections.cpp
index bcf3b6693ef..20e2052305a 100644
--- a/lld/ELF/SyntheticSections.cpp
+++ b/lld/ELF/SyntheticSections.cpp
@@ -472,7 +472,7 @@ std::vector<EhFrameSection::FdeData> EhFrameSection::getFdeData() const {
   auto Less = [](const FdeData &A, const FdeData &B) {
     return A.PcRel < B.PcRel;
   };
-  std::stable_sort(Ret.begin(), Ret.end(), Less);
+  llvm::stable_sort(Ret, Less);
   auto Eq = [](const FdeData &A, const FdeData &B) {
     return A.PcRel == B.PcRel;
   };
@@ -1498,7 +1498,7 @@ static bool compRelocations(const DynamicReloc &A, const DynamicReloc &B) {
 
 template <class ELFT> void RelocationSection<ELFT>::writeTo(uint8_t *Buf) {
   if (Sort)
-    std::stable_sort(Relocs.begin(), Relocs.end(), compRelocations);
+    llvm::stable_sort(Relocs, compRelocations);
 
   for (const DynamicReloc &Rel : Relocs) {
     encodeDynamicReloc<ELFT>(reinterpret_cast<Elf_Rela *>(Buf), Rel);
@@ -1831,7 +1831,7 @@ void SymbolTableBaseSection::finalizeContents() {
     // NB: It also sorts Symbols to meet the GNU hash table requirements.
     In.GnuHashTab->addSymbols(Symbols);
   } else if (Config->EMachine == EM_MIPS) {
-    std::stable_sort(Symbols.begin(), Symbols.end(), sortMipsSymbols);
+    llvm::stable_sort(Symbols, sortMipsSymbols);
   }
 
   size_t I = 0;
@@ -2199,9 +2199,9 @@ void GnuHashTableSection::addSymbols(std::vector<SymbolTableEntry> &V) {
     Symbols.push_back({B, Ent.StrTabOffset, Hash, BucketIdx});
   }
 
-  std::stable_sort(
-      Symbols.begin(), Symbols.end(),
-      [](const Entry &L, const Entry &R) { return L.BucketIdx < R.BucketIdx; });
+  llvm::stable_sort(Symbols, [](const Entry &L, const Entry &R) {
+    return L.BucketIdx < R.BucketIdx;
+  });
 
   V.erase(Mid, V.end());
   for (const Entry &Ent : Symbols)
@@ -3088,8 +3088,7 @@ void ARMExidxSyntheticSection::finalizeContents() {
       return AOut->SectionIndex < BOut->SectionIndex;
     return A->OutSecOff < B->OutSecOff;
   };
-  std::stable_sort(ExecutableSections.begin(), ExecutableSections.end(),
-                   CompareByFilePosition);
+  llvm::stable_sort(ExecutableSections, CompareByFilePosition);
   Sentinel = ExecutableSections.back();
   // Optionally merge adjacent duplicate entries.
   if (Config->MergeArmExidx) {
diff --git a/lld/ELF/Writer.cpp b/lld/ELF/Writer.cpp
index dc7ed19baa6..2903664d3af 100644
--- a/lld/ELF/Writer.cpp
+++ b/lld/ELF/Writer.cpp
@@ -1280,11 +1280,11 @@ static void sortSection(OutputSection *Sec,
       return;
     assert(Sec->SectionCommands.size() == 1);
     auto *ISD = cast<InputSectionDescription>(Sec->SectionCommands[0]);
-    std::stable_sort(ISD->Sections.begin(), ISD->Sections.end(),
-                     [](const InputSection *A, const InputSection *B) -> bool {
-                       return A->File->PPC64SmallCodeModelTocRelocs &&
-                              !B->File->PPC64SmallCodeModelTocRelocs;
-                     });
+    llvm::stable_sort(ISD->Sections,
+                      [](const InputSection *A, const InputSection *B) -> bool {
+                        return A->File->PPC64SmallCodeModelTocRelocs &&
+                               !B->File->PPC64SmallCodeModelTocRelocs;
+                      });
     return;
   }
 
@@ -1453,7 +1453,7 @@ template <class ELFT> void Writer<ELFT>::resolveShfLinkOrder() {
         Sec->Type == SHT_ARM_EXIDX)
       continue;
 
-    std::stable_sort(Sections.begin(), Sections.end(), compareByFilePosition);
+    llvm::stable_sort(Sections, compareByFilePosition);
 
     for (int I = 0, N = Sections.size(); I < N; ++I)
       *ScriptSections[I] = Sections[I];
diff --git a/lld/lib/ReaderWriter/MachO/MachOLinkingContext.cpp b/lld/lib/ReaderWriter/MachO/MachOLinkingContext.cpp
index a9683d00b51..38456024c9f 100644
--- a/lld/lib/ReaderWriter/MachO/MachOLinkingContext.cpp
+++ b/lld/lib/ReaderWriter/MachO/MachOLinkingContext.cpp
@@ -1014,11 +1014,10 @@ static bool isLibrary(const std::unique_ptr<Node> &elem) {
 // new undefines from libraries.
 void MachOLinkingContext::finalizeInputFiles() {
   std::vector<std::unique_ptr<Node>> &elements = getNodes();
-  std::stable_sort(elements.begin(), elements.end(),
-                   [](const std::unique_ptr<Node> &a,
-                      const std::unique_ptr<Node> &b) {
-                     return !isLibrary(a) && isLibrary(b);
-                   });
+  llvm::stable_sort(elements, [](const std::unique_ptr<Node> &a,
+                                 const std::unique_ptr<Node> &b) {
+    return !isLibrary(a) && isLibrary(b);
+  });
   size_t numLibs = std::count_if(elements.begin(), elements.end(), isLibrary);
   elements.push_back(llvm::make_unique<GroupEnd>(numLibs));
 }
diff --git a/lld/wasm/Writer.cpp b/lld/wasm/Writer.cpp
index d4014d7b894..47e76748f79 100644
--- a/lld/wasm/Writer.cpp
+++ b/lld/wasm/Writer.cpp
@@ -1402,10 +1402,10 @@ void Writer::calculateInitFunctions() {
 
   // Sort in order of priority (lowest first) so that they are called
   // in the correct order.
-  std::stable_sort(InitFunctions.begin(), InitFunctions.end(),
-                   [](const WasmInitEntry &L, const WasmInitEntry &R) {
-                     return L.Priority < R.Priority;
-                   });
+  llvm::stable_sort(InitFunctions,
+                    [](const WasmInitEntry &L, const WasmInitEntry &R) {
+                      return L.Priority < R.Priority;
+                    });
 }
 
 void Writer::run() {