From de83cbf37e8ac59d405b4d3ea2ce389e619bc901 Mon Sep 17 00:00:00 2001
From: George Rimar <grimar@accesssoftek.com>
Date: Tue, 24 Apr 2018 09:55:39 +0000
Subject: [PATCH] [ELF] - Never use std::sort.

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

Differential revision: https://reviews.llvm.org/D45969

llvm-svn: 330702
---
 lld/ELF/CallGraphSort.cpp     |  8 ++++----
 lld/ELF/MapFile.cpp           |  5 +++--
 lld/ELF/SyntheticSections.cpp | 16 ++++++++--------
 lld/ELF/Writer.cpp            | 10 +++++-----
 4 files changed, 20 insertions(+), 19 deletions(-)

diff --git a/lld/ELF/CallGraphSort.cpp b/lld/ELF/CallGraphSort.cpp
index 3d9558c..33ac159 100644
--- a/lld/ELF/CallGraphSort.cpp
+++ b/lld/ELF/CallGraphSort.cpp
@@ -219,10 +219,10 @@ void CallGraphSort::groupClusters() {
   });
 
   // Sort by density.
-  std::sort(Clusters.begin(), Clusters.end(),
-            [](const Cluster &A, const Cluster &B) {
-              return A.getDensity() > B.getDensity();
-            });
+  std::stable_sort(Clusters.begin(), Clusters.end(),
+                   [](const Cluster &A, const Cluster &B) {
+                     return A.getDensity() > B.getDensity();
+                   });
 }
 
 DenseMap<const InputSectionBase *, int> CallGraphSort::run() {
diff --git a/lld/ELF/MapFile.cpp b/lld/ELF/MapFile.cpp
index b7886fe..4e8e045 100644
--- a/lld/ELF/MapFile.cpp
+++ b/lld/ELF/MapFile.cpp
@@ -90,8 +90,9 @@ static SymbolMapTy getSectionSyms(ArrayRef<Symbol *> Syms) {
   // 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;
 }
diff --git a/lld/ELF/SyntheticSections.cpp b/lld/ELF/SyntheticSections.cpp
index c534cfd..08c9142 100644
--- a/lld/ELF/SyntheticSections.cpp
+++ b/lld/ELF/SyntheticSections.cpp
@@ -1393,10 +1393,10 @@ bool AndroidPackedRelocationSection<ELFT>::updateAllocSize() {
       NonRelatives.push_back(R);
   }
 
-  std::sort(Relatives.begin(), Relatives.end(),
-            [](const Elf_Rel &A, const Elf_Rel &B) {
-              return A.r_offset < B.r_offset;
-            });
+  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
@@ -1474,10 +1474,10 @@ bool AndroidPackedRelocationSection<ELFT>::updateAllocSize() {
   }
 
   // Finally the non-relative relocations.
-  std::sort(NonRelatives.begin(), NonRelatives.end(),
-            [](const Elf_Rela &A, const Elf_Rela &B) {
-              return A.r_offset < B.r_offset;
-            });
+  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);
diff --git a/lld/ELF/Writer.cpp b/lld/ELF/Writer.cpp
index ae5b580..e4a0e61 100644
--- a/lld/ELF/Writer.cpp
+++ b/lld/ELF/Writer.cpp
@@ -1106,7 +1106,7 @@ sortISDBySectionOrder(InputSectionDescription *ISD,
     }
     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;
@@ -2056,10 +2056,10 @@ struct SectionOffset {
 // 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(),
-            [=](const SectionOffset &A, const SectionOffset &B) {
-              return A.Offset < B.Offset;
-            });
+  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.
-- 
2.7.4