Index: lld/COFF/ICF.cpp
===================================================================
--- lld/COFF/ICF.cpp
+++ lld/COFF/ICF.cpp
@@ -41,8 +41,8 @@
 private:
   void segregate(size_t Begin, size_t End, bool Constant);
 
-  bool equalsConstant(const SectionChunk *A, const SectionChunk *B);
-  bool equalsVariable(const SectionChunk *A, const SectionChunk *B);
+  bool lessConstant(const SectionChunk *A, const SectionChunk *B);
+  bool lessVariable(const SectionChunk *A, const SectionChunk *B);
 
   uint32_t getHash(SectionChunk *C);
   bool isEligible(SectionChunk *C);
@@ -86,78 +86,117 @@
 
 // Split an equivalence class into smaller classes.
 void ICF::segregate(size_t Begin, size_t End, bool Constant) {
+  auto Less = [&](SectionChunk *L, SectionChunk *R) {
+    if (Constant)
+      return lessConstant(L, R);
+    return lessVariable(L, R);
+  };
+
+  // Group equal chunks together and then split [Begin, End) range into smaller
+  // ranges with equal values
+  std::stable_sort(Chunks.begin() + Begin, Chunks.begin() + End, Less);
+
   while (Begin < End) {
-    // Divide [Begin, End) into two. Let Mid be the start index of the
-    // second group.
-    auto Bound = std::stable_partition(
-        Chunks.begin() + Begin + 1, Chunks.begin() + End, [&](SectionChunk *S) {
-          if (Constant)
-            return equalsConstant(Chunks[Begin], S);
-          return equalsVariable(Chunks[Begin], S);
-        });
-    size_t Mid = Bound - Chunks.begin();
-
-    // Split [Begin, End) into [Begin, Mid) and [Mid, End). We use Mid as an
+    // Find a sequence of elements that belong to the same equivalence class.
+    size_t I = Begin + 1;
+    while (I < End && !Less(Chunks[Begin], Chunks[I]))
+      ++I;
+
+    // Split [Begin, End) into [Begin, I) and [I, End). We use I as an
     // equivalence class ID because every group ends with a unique index.
-    for (size_t I = Begin; I < Mid; ++I)
-      Chunks[I]->Class[(Cnt + 1) % 2] = Mid;
+    for (size_t J = Begin; J < I; ++J)
+      Chunks[J]->Class[(Cnt + 1) % 2] = I;
 
     // If we created a group, we need to iterate the main loop again.
-    if (Mid != End)
+    if (I != End)
       Repeat = true;
-
-    Begin = Mid;
+    Begin = I;
   }
 }
 
 // Compare "non-moving" part of two sections, namely everything
 // except relocation targets.
-bool ICF::equalsConstant(const SectionChunk *A, const SectionChunk *B) {
+bool ICF::lessConstant(const SectionChunk *A, const SectionChunk *B) {
   if (A->NumRelocs != B->NumRelocs)
-    return false;
+    return A->NumRelocs < B->NumRelocs;
+
+  if (A->getPermissions() != B->getPermissions())
+    return A->getPermissions() < B->getPermissions();
+
+  if (A->SectionName != B->SectionName)
+    return A->SectionName < B->SectionName;
+
+  if (A->getAlign() != B->getAlign())
+    return A->getAlign() < B->getAlign();
+
+  if (A->Header->SizeOfRawData != B->Header->SizeOfRawData)
+    return A->Header->SizeOfRawData < B->Header->SizeOfRawData;
+
+  if (A->Checksum != B->Checksum)
+    return A->Checksum < B->Checksum;
+
+  if (int X =
+          toStringRef(A->getContents()).compare(toStringRef(B->getContents())))
+    return X < 0;
 
   // Compare relocations.
-  auto Eq = [&](const coff_relocation &R1, const coff_relocation &R2) {
-    if (R1.Type != R2.Type ||
-        R1.VirtualAddress != R2.VirtualAddress) {
-      return false;
-    }
+  for (size_t I = 0; I != A->NumRelocs; ++I) {
+    const coff_relocation &R1 = *(A->Relocs.begin() + I);
+    const coff_relocation &R2 = *(B->Relocs.begin() + I);
+
+    if (R1.Type != R2.Type)
+      return R1.Type < R2.Type;
+    if (R1.VirtualAddress != R2.VirtualAddress)
+      return R1.VirtualAddress < R2.VirtualAddress;
+
     SymbolBody *B1 = A->File->getSymbolBody(R1.SymbolTableIndex);
     SymbolBody *B2 = B->File->getSymbolBody(R2.SymbolTableIndex);
     if (B1 == B2)
-      return true;
-    if (auto *D1 = dyn_cast<DefinedRegular>(B1))
-      if (auto *D2 = dyn_cast<DefinedRegular>(B2))
-        return D1->getValue() == D2->getValue() &&
-               D1->getChunk()->Class[Cnt % 2] == D2->getChunk()->Class[Cnt % 2];
-    return false;
-  };
-  if (!std::equal(A->Relocs.begin(), A->Relocs.end(), B->Relocs.begin(), Eq))
-    return false;
-
-  // Compare section attributes and contents.
-  return A->getPermissions() == B->getPermissions() &&
-         A->SectionName == B->SectionName &&
-         A->getAlign() == B->getAlign() &&
-         A->Header->SizeOfRawData == B->Header->SizeOfRawData &&
-         A->Checksum == B->Checksum &&
-         A->getContents() == B->getContents();
+      continue;
+
+    auto *D1 = dyn_cast<DefinedRegular>(B1);
+    auto *D2 = dyn_cast<DefinedRegular>(B2);
+
+    if (!D1 || !D2)
+      return B1 < B2;
+
+    if (D1->getValue() != D2->getValue())
+      return D1->getValue() < D2->getValue();
+
+    uint32_t C1 = D1->getChunk()->Class[Cnt % 2];
+    uint32_t C2 = D2->getChunk()->Class[Cnt % 2];
+    if (C1 != C2)
+      return C1 < C2;
+  }
+
+  return false;
 }
 
 // Compare "moving" part of two sections, namely relocation targets.
-bool ICF::equalsVariable(const SectionChunk *A, const SectionChunk *B) {
+bool ICF::lessVariable(const SectionChunk *A, const SectionChunk *B) {
   // Compare relocations.
-  auto Eq = [&](const coff_relocation &R1, const coff_relocation &R2) {
+  for (size_t I = 0; I != A->NumRelocs; ++I) {
+    const coff_relocation &R1 = *(A->Relocs.begin() + I);
+    const coff_relocation &R2 = *(B->Relocs.begin() + I);
+
     SymbolBody *B1 = A->File->getSymbolBody(R1.SymbolTableIndex);
     SymbolBody *B2 = B->File->getSymbolBody(R2.SymbolTableIndex);
     if (B1 == B2)
-      return true;
-    if (auto *D1 = dyn_cast<DefinedRegular>(B1))
-      if (auto *D2 = dyn_cast<DefinedRegular>(B2))
-        return D1->getChunk()->Class[Cnt % 2] == D2->getChunk()->Class[Cnt % 2];
-    return false;
-  };
-  return std::equal(A->Relocs.begin(), A->Relocs.end(), B->Relocs.begin(), Eq);
+      continue;
+
+    auto *D1 = dyn_cast<DefinedRegular>(B1);
+    auto *D2 = dyn_cast<DefinedRegular>(B2);
+
+    if (!D1 || !D2)
+      return B1 < B2;
+
+    uint32_t C1 = D1->getChunk()->Class[Cnt % 2];
+    uint32_t C2 = D2->getChunk()->Class[Cnt % 2];
+    if (C1 != C2)
+      return C1 < C2;
+  }
+
+  return false;
 }
 
 size_t ICF::findBoundary(size_t Begin, size_t End) {
@@ -169,11 +208,8 @@
 
 void ICF::forEachClassRange(size_t Begin, size_t End,
                             std::function<void(size_t, size_t)> Fn) {
-  if (Begin > 0)
-    Begin = findBoundary(Begin - 1, End);
-
   while (Begin < End) {
-    size_t Mid = findBoundary(Begin, Chunks.size());
+    size_t Mid = findBoundary(Begin, End);
     Fn(Begin, Mid);
     Begin = Mid;
   }
@@ -190,11 +226,21 @@
   }
 
   // Split sections into 256 shards and call Fn in parallel.
-  size_t NumShards = 256;
+  constexpr size_t NumShards = 256;
   size_t Step = Chunks.size() / NumShards;
+  std::array<size_t, NumShards + 1> Bounds;
+  for (size_t I = 0; I < NumShards; I++) {
+    size_t Bound = I * Step;
+    if (Bound > 0)
+      Bound = findBoundary(Bound - 1, Chunks.size());
+
+    Bounds[I] = Bound;
+  };
+
+  Bounds[NumShards] = Chunks.size();
+
   for_each_n(parallel::par, size_t(0), NumShards, [&](size_t I) {
-    size_t End = (I == NumShards - 1) ? Chunks.size() : (I + 1) * Step;
-    forEachClassRange(I * Step, End, Fn);
+    forEachClassRange(Bounds[I], Bounds[I + 1], Fn);
   });
   ++Cnt;
 }
Index: lld/COFF/Writer.cpp
===================================================================
--- lld/COFF/Writer.cpp
+++ lld/COFF/Writer.cpp
@@ -875,14 +875,16 @@
   uint8_t *End = Begin + Sec->getVirtualSize();
   if (Config->Machine == AMD64) {
     struct Entry { ulittle32_t Begin, End, Unwind; };
-    sort(parallel::par, (Entry *)Begin, (Entry *)End,
-         [](const Entry &A, const Entry &B) { return A.Begin < B.Begin; });
+    std::stable_sort(
+        (Entry *)Begin, (Entry *)End,
+        [](const Entry &A, const Entry &B) { return A.Begin < B.Begin; });
     return;
   }
   if (Config->Machine == ARMNT) {
     struct Entry { ulittle32_t Begin, Unwind; };
-    sort(parallel::par, (Entry *)Begin, (Entry *)End,
-         [](const Entry &A, const Entry &B) { return A.Begin < B.Begin; });
+    std::stable_sort(
+        (Entry *)Begin, (Entry *)End,
+        [](const Entry &A, const Entry &B) { return A.Begin < B.Begin; });
     return;
   }
   errs() << "warning: don't know how to handle .pdata.\n";