Use llvm::stable_sort

[MaskRay]

Summary

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

[ruiu]

LGTM

Nice!

lld/trunk/COFF/ICF.cpp

parallelForEach(Chunks, [&](SectionChunk *SC) {
           Hash += Sym->getChunk()->Class[Cnt % 2];
       // Set MSB to 1 to avoid collisions with non-hash classs.
       SC->Class[(Cnt + 1) % 2] = Hash | (1U << 31);
     });
   }
 
   // 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) {
 
   // Compare static contents and assign unique IDs for each static content.
   forEachClass([&](size_t Begin, size_t End) { segregate(Begin, End, true); });
 
   // Split groups by comparing relocations until convergence is obtained.
   do {
     Repeat = false;
     forEachClass(

lld/trunk/COFF/Writer.cpp

 static void sortBySectionOrder(std::vector<Chunk *> &Chunks) {
   auto GetPriority = [](const Chunk *C) {
     if (auto *Sec = dyn_cast<SectionChunk>(C))
       if (Sec->Sym)
         return Config->Order.lookup(Sec->Sym->getName());
     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) {
 }
 
 // Sort concrete section chunks from GNU import libraries.
 //
 // GNU binutils doesn't use short import files, but instead produces import
 // libraries that consist of object files, with section chunks for the .idata$*
 // sections. These are linked just as regular static libraries. Each import
 // library consists of one header object, one object file for every imported
bool Writer::fixGnuImportChunks() {
   bool HasIdata = false;
   // Sort all .idata$* chunks, grouping chunks from the same library,
   // with alphabetical ordering of the object fils within a library.
   for (auto It : PartialSections) {
     PartialSection *PSec = It.second;
     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) {
         // if SC1, order them ascending. If SC2 or both null,
         // S is not less than T.
         return SC1 != nullptr;
       }
       // Make a string with "libraryname/objectfile" for sorting, achieving
for (auto It : PartialSections) {
     OutputSection *Sec = CreateSection(Name, OutChars);
     for (Chunk *C : PSec->Chunks)
       Sec->addChunk(C);
 
     Sec->addContributingPartialSection(PSec);
   }
 
   // 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).
     if (S->Header.Characteristics & IMAGE_SCN_MEM_DISCARDABLE)
       return 2;
     // .rsrc should come at the end of the non-discardable sections because its
     // size may change by the Win32 UpdateResources() function, causing
     // subsequent sections to move (see https://crbug.com/827082).
     if (S == RsrcSec)
       return 1;
     return 0;
   };
-  std::stable_sort(OutputSections.begin(), OutputSections.end(),
-                   [&](OutputSection *S, OutputSection *T) {
+  llvm::stable_sort(OutputSections,
+                    [&](const OutputSection *S, const OutputSection *T) {
                       return SectionOrder(S) < SectionOrder(T);
                     });
 }
 
 void Writer::createMiscChunks() {
   for (auto &P : MergeChunk::Instances)
     RdataSec->addChunk(P.second);
 
   // Create thunks for locally-dllimported symbols.
   if (!Symtab->LocalImportChunks.empty()) {
auto SectionChunkOrder = [](const Chunk *A, const Chunk *B) {
     auto SB = dyn_cast<SectionChunk>(B);
     assert(SA && SB && "Non-section chunks in CRT section!");
 
     StringRef SAObj = SA->File->MB.getBufferIdentifier();
     StringRef SBObj = SB->File->MB.getBufferIdentifier();
 
     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) {
       auto SC = dyn_cast<SectionChunk>(C);
       log("  " + SC->File->MB.getBufferIdentifier().str() +
           ", SectionID: " + Twine(SC->getSectionNumber()));
     }
   }

lld/trunk/ELF/AArch64ErrataFix.cpp

void AArch64Err843419Patcher::init() {
   // For each InputSection make sure the mapping symbols are in sorted in
   // ascending order and free from consecutive runs of mapping symbols with
   // the same type. For example we must remove the redundant $d.1 from $x.0
   // $d.0 $d.1 $x.1.
   for (auto &KV : SectionMap) {
     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) {
                       return (IsCodeMapSymbol(A) && IsCodeMapSymbol(B)) ||
                              (IsDataMapSymbol(A) && IsDataMapSymbol(B));
                     }),
         MapSyms.end());
   }

lld/trunk/ELF/CallGraphSort.cpp

void CallGraphSort::groupClusters() {
   std::vector<int> SortedSecs(Clusters.size());
   std::vector<Cluster *> SecToCluster(Clusters.size());
 
   for (size_t I = 0; I < Clusters.size(); ++I) {
     SortedSecs[I] = I;
     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) {
     // Clusters[SI] is the same as SecToClusters[SI] here because it has not
     // been merged into another cluster yet.
     Cluster &C = Clusters[SI];
 
     // Don't consider merging if the edge is unlikely.
void CallGraphSort::groupClusters() {
   }
 
   // Remove empty or dead nodes. Invalidates all cluster indices.
   llvm::erase_if(Clusters, [](const Cluster &C) {
     return C.Size == 0 || C.Sections.empty();
   });
 
   // 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) {
 }
 
 DenseMap<const InputSectionBase *, int> CallGraphSort::run() {
   groupClusters();
 
   // Generate order.
   DenseMap<const InputSectionBase *, int> OrderMap;
   ssize_t CurOrder = 1;

lld/trunk/ELF/ICF.cpp

parallelForEach(Sections, [&](InputSection *S) {
         combineRelocHashes<ELFT>(Cnt, S, S->template relas<ELFT>());
       else
         combineRelocHashes<ELFT>(Cnt, S, S->template rels<ELFT>());
     });
   }
 
   // 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) {
 
   // Compare static contents and assign unique IDs for each static content.
   forEachClass([&](size_t Begin, size_t End) { segregate(Begin, End, true); });
 
   // Split groups by comparing relocations until convergence is obtained.
   do {
     Repeat = false;
     forEachClass(

lld/trunk/ELF/LinkerScript.cpp

static bool matchConstraints(ArrayRef<InputSection *> Sections,
 
   return (IsRW && Kind == ConstraintKind::ReadWrite) ||
          (!IsRW && Kind == ConstraintKind::ReadOnly);
 }
 
 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
 // option. Because SORT-family commands can be nested at most two depth
 // (e.g. SORT_BY_NAME(SORT_BY_ALIGNMENT(.text.*))) and because the command
 // line option is respected even if a SORT command is given, the exact
 // behavior we have here is a bit complicated. Here are the rules.
 //

lld/trunk/ELF/MapFile.cpp

 static SymbolMapTy getSectionSyms(ArrayRef<Defined *> Syms) {
   SymbolMapTy Ret;
   for (Defined *DR : Syms)
     Ret[DR->Section].push_back(DR);
 
   // 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;
 }
 
 // Construct a map from symbols to their stringified representations.
 // Demangling symbols (which is what toString() does) is slow, so
 // we do that in batch using parallel-for.
 static DenseMap<Symbol *, std::string>
 getSymbolStrings(ArrayRef<Defined *> Syms) {

lld/trunk/ELF/OutputSections.cpp

if (SectionCommands.empty() ||
       SectionCommands.push_back(make<InputSectionDescription>(""));
     auto *ISD = cast<InputSectionDescription>(SectionCommands.back());
     ISD->Sections.push_back(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;
 }
 
 uint64_t elf::getHeaderSize() {
   if (Config->OFormatBinary)
     return 0;

 }
 
 // Sorts input sections by the special rules for .ctors and .dtors.
 // Unfortunately, the rules are different from the one for .{init,fini}_array.
 // Read the comment above.
 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,
 // return N. Otherwise, returns 65536, which is one greater than the
 // lowest priority.
 int elf::getPriority(StringRef S) {
   size_t Pos = S.rfind('.');
   if (Pos == StringRef::npos)

lld/trunk/ELF/Relocations.cpp

static void scanRelocs(InputSectionBase &Sec, ArrayRef<RelTy> Rels) {
   // Not all relocations end up in Sec.Relocations, but a lot do.
   Sec.Relocations.reserve(Rels.size());
 
   for (auto I = Rels.begin(), End = Rels.end(); I != End;)
     scanReloc<ELFT>(Sec, GetOffset, I, End);
 
   // 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(),
+    llvm::stable_sort(Sec.Relocations,
                       [](const Relocation &LHS, const Relocation &RHS) {
                         return LHS.Offset < RHS.Offset;
                       });
 }
 
 template <class ELFT> void elf::scanRelocations(InputSectionBase &S) {
   if (S.AreRelocsRela)
     scanRelocs<ELFT>(S, S.relas<ELFT>());
   else
     scanRelocs<ELFT>(S, S.rels<ELFT>());
 }
forEachInputSectionDescription(
 
         // ISD->ThunkSections contains all created ThunkSections, including
         // those inserted in previous passes. Extract the Thunks created this
         // pass and order them in ascending OutSecOff.
         std::vector<ThunkSection *> NewThunks;
         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(),
+        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;
         Tmp.reserve(ISD->Sections.size() + NewThunks.size());
 
         std::merge(ISD->Sections.begin(), ISD->Sections.end(),
                    NewThunks.begin(), NewThunks.end(), std::back_inserter(Tmp),
                    mergeCmp);

lld/trunk/ELF/SyntheticSections.cpp

std::vector<EhFrameSection::FdeData> EhFrameSection::getFdeData() const {
   }
 
   // Sort the FDE list by their PC and uniqueify. Usually there is only
   // one FDE for a PC (i.e. function), but if ICF merges two functions
   // into one, there can be more than one FDEs pointing to the address.
   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;
   };
   Ret.erase(std::unique(Ret.begin(), Ret.end(), Eq), Ret.end());
 
   return Ret;
 }
 
static bool compRelocations(const DynamicReloc &A, const DynamicReloc &B) {
   bool BIsRel = B.Type == Target->RelativeRel;
   if (AIsRel != BIsRel)
     return AIsRel;
   return A.getSymIndex() < B.getSymIndex();
 }
 
 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);
     Buf += Config->IsRela ? sizeof(Elf_Rela) : sizeof(Elf_Rel);
   }
 }
 
 template <class ELFT>
void SymbolTableBaseSection::finalizeContents() {
   // Section's Info field has the index of the first non-local symbol.
   // Because the first symbol entry is a null entry, 1 is the first.
   getParent()->Info = 1;
 
   if (In.GnuHashTab) {
     // 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;
   for (const SymbolTableEntry &S : Symbols)
     S.Sym->DynsymIndex = ++I;
 }
 
 // The ELF spec requires that all local symbols precede global symbols, so we
void GnuHashTableSection::addSymbols(std::vector<SymbolTableEntry> &V) {
 
   for (SymbolTableEntry &Ent : llvm::make_range(Mid, V.end())) {
     Symbol *B = Ent.Sym;
     uint32_t Hash = hashGnu(B->getName());
     uint32_t BucketIdx = Hash % NBuckets;
     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)
     V.push_back({Ent.Sym, Ent.StrTabOffset});
 }
 
 HashTableSection::HashTableSection()
     : SyntheticSection(SHF_ALLOC, SHT_HASH, 4, ".hash") {
auto CompareByFilePosition = [](const InputSection *A,
                                   const InputSection *B) {
     OutputSection *AOut = A->getParent();
     OutputSection *BOut = B->getParent();
 
     if (AOut != BOut)
       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) {
     std::vector<InputSection *> SelectedSections;
     SelectedSections.reserve(ExecutableSections.size());
     SelectedSections.push_back(ExecutableSections[0]);
     size_t Prev = 0;
     for (size_t I = 1; I < ExecutableSections.size(); ++I) {

lld/trunk/ELF/Writer.cpp

static void sortSection(OutputSection *Sec,
   // addressable range of [.got, .got + 0xFFFC] for GOT-relative relocations.
   // To reduce the risk of relocation overflow, .toc contents are sorted so that
   // sections having smaller relocation offsets are at beginning of .toc
   if (Config->EMachine == EM_PPC64 && Name == ".toc") {
     if (Script->HasSectionsCommand)
       return;
     assert(Sec->SectionCommands.size() == 1);
     auto *ISD = cast<InputSectionDescription>(Sec->SectionCommands[0]);
-    std::stable_sort(ISD->Sections.begin(), ISD->Sections.end(),
+    llvm::stable_sort(ISD->Sections,
                       [](const InputSection *A, const InputSection *B) -> bool {
                         return A->File->PPC64SmallCodeModelTocRelocs &&
                                !B->File->PPC64SmallCodeModelTocRelocs;
                       });
     return;
   }
 
   // Sort input sections by priority using the list provided
   // by --symbol-ordering-file.
   if (!Order.empty())
     for (BaseCommand *B : Sec->SectionCommands)
       if (auto *ISD = dyn_cast<InputSectionDescription>(B))
for (OutputSection *Sec : OutputSections) {
     }
 
     // The ARM.exidx section use SHF_LINK_ORDER, but we have consolidated
     // this processing inside the ARMExidxsyntheticsection::finalizeContents().
     if (!Config->Relocatable && Config->EMachine == EM_ARM &&
         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];
   }
 }
 
 // We need to generate and finalize the content that depends on the address of
 // InputSections. As the generation of the content may also alter InputSection

lld/trunk/lib/ReaderWriter/MachO/MachOLinkingContext.cpp

 // links in all object (.o) files in command line order. The second phase
 // links in libraries in command line order.
 // In this function we reorder the input files so that all the object files
 // comes before any library file. We also make a group for the library files
 // so that the Resolver will reiterate over the libraries as long as we find
 // 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,
+  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));
 }
 
 llvm::Error MachOLinkingContext::handleLoadedFile(File &file) {
   auto *machoFile = dyn_cast<MachOFile>(&file);
   if (!machoFile)
     return llvm::Error::success();

lld/trunk/wasm/Writer.cpp

for (const WasmInitFunc &F : L.InitFunctions) {
       if (*Sym->Signature != WasmSignature{{}, {}})
         error("invalid signature for init func: " + toString(*Sym));
       InitFunctions.emplace_back(WasmInitEntry{Sym, F.Priority});
     }
   }
 
   // Sort in order of priority (lowest first) so that they are called
   // in the correct order.
-  std::stable_sort(InitFunctions.begin(), InitFunctions.end(),
+  llvm::stable_sort(InitFunctions,
                     [](const WasmInitEntry &L, const WasmInitEntry &R) {
                       return L.Priority < R.Priority;
                     });
 }
 
 void Writer::run() {
   if (Config->Relocatable || Config->Pic)
     Config->GlobalBase = 0;
 
   // For PIC code the table base is assigned dynamically by the loader.
   // For non-PIC, we start at 1 so that accessing table index 0 always traps.