[ELF] - Never use std::sort.

[grimar]

Summary

It turns out we should not use the std::sort anymore.
r327219 added a new wrapper llvm::sort (D39245).
When EXPENSIVE_CHECKS is defined, it shuffles the
input container and that helps to find non-deterministic
ordering.

Patch changes code to use llvm::sort and std::stable_sort
instead of std::sort

[• espindola]

LGTM

ELF/CallGraphSort.cpp

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::sort(Clusters.begin(), Clusters.end(),
+  std::stable_sort(Clusters.begin(), Clusters.end(),
                    [](const Cluster &A, const Cluster &B) {
                      return A.getDensity() > B.getDensity();
                    });
 }
 
 DenseMap<const InputSectionBase *, int> CallGraphSort::run() {
   groupClusters();
 
   // Generate order.
   llvm::DenseMap<const InputSectionBase *, int> OrderMap;
   ssize_t CurOrder = 1;

ELF/MapFile.cpp

else
       Ret[InX::Plt].push_back(S);
   }
 
   // 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<Symbol *> &V = It.second;
-    std::sort(V.begin(), V.end(),
-              [](Symbol *A, Symbol *B) { return A->getVA() < B->getVA(); });
+    std::stable_sort(V.begin(), V.end(), [](Symbol *A, Symbol *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>

ELF/SyntheticSections.cpp

for (const DynamicReloc &Rel : Relocs) {
     encodeDynamicReloc<ELFT>(&R, Rel);
 
     if (R.getType(Config->IsMips64EL) == Target->RelativeRel)
       Relatives.push_back(R);
     else
       NonRelatives.push_back(R);
   }
 
-  std::sort(Relatives.begin(), Relatives.end(),
+  llvm::sort(Relatives.begin(), Relatives.end(),
              [](const Elf_Rel &A, const Elf_Rel &B) {
                return A.r_offset < B.r_offset;
              });
 
   // Try to find groups of relative relocations which are spaced one word
   // apart from one another. These generally correspond to vtable entries. The
   // format allows these groups to be encoded using a sort of run-length
   // encoding, but each group will cost 7 bytes in addition to the offset from
   // the previous group, so it is only profitable to do this for groups of
   // size 8 or larger.
   std::vector<Elf_Rela> UngroupedRelatives;
for (Elf_Rela &R : UngroupedRelatives) {
       if (Config->IsRela) {
         Add(R.r_addend - Addend);
         Addend = R.r_addend;
       }
     }
   }
 
   // Finally the non-relative relocations.
-  std::sort(NonRelatives.begin(), NonRelatives.end(),
+  llvm::sort(NonRelatives.begin(), NonRelatives.end(),
              [](const Elf_Rela &A, const Elf_Rela &B) {
                return A.r_offset < B.r_offset;
              });
   if (!NonRelatives.empty()) {
     Add(NonRelatives.size());
     Add(HasAddendIfRela);
     for (Elf_Rela &R : NonRelatives) {
       Add(R.r_offset - Offset);
       Offset = R.r_offset;
       Add(R.r_info);
       if (Config->IsRela) {

ELF/Writer.cpp

for (InputSection *IS : ISD->Sections) {
     auto I = Order.find(IS);
     if (I == Order.end()) {
       UnorderedSections.push_back(IS);
       UnorderedSize += IS->getSize();
       continue;
     }
     OrderedSections.push_back({IS, I->second});
   }
-  std::sort(
+  llvm::sort(
       OrderedSections.begin(), OrderedSections.end(),
       [&](std::pair<InputSection *, int> A, std::pair<InputSection *, int> B) {
         return A.second < B.second;
       });
 
   // Find an insertion point for the ordered section list in the unordered
   // section list. On targets with limited-range branches, this is the mid-point
   // of the unordered section list. This decreases the likelihood that a range
struct SectionOffset {
   OutputSection *Sec;
   uint64_t Offset;
 };
 } // namespace
 
 // Check whether sections overlap for a specific address range (file offsets,
 // load and virtual adresses).
 static void checkOverlap(StringRef Name, std::vector<SectionOffset> &Sections) {
-  std::sort(Sections.begin(), Sections.end(),
+  llvm::sort(Sections.begin(), Sections.end(),
              [=](const SectionOffset &A, const SectionOffset &B) {
                return A.Offset < B.Offset;
              });
 
   // Finding overlap is easy given a vector is sorted by start position.
   // If an element starts before the end of the previous element, they overlap.
   for (size_t I = 1, End = Sections.size(); I < End; ++I) {
     SectionOffset A = Sections[I - 1];
     SectionOffset B = Sections[I];
     if (B.Offset < A.Offset + A.Sec->Size)
       errorOrWarn(