[ELF] Optimize -z combreloc

Sorting dynamic relocations is a bottleneck. Simplifying the comparator improves
performance. Linking clang is 4~5% faster with --threads=8.

This change may shuffle R_MIPS_REL32 for Mips and is a NFC for non-Mips.

1 files changed, 8 insertions, 3 deletions

diff --git a/lld/ELF/SyntheticSections.cpp b/lld/ELF/SyntheticSections.cpp
index f41459d..aef6434 100644
--- a/lld/ELF/SyntheticSections.cpp
+++ b/lld/ELF/SyntheticSections.cpp
@@ -1709,9 +1709,14 @@ template <class ELFT> void RelocationSection<ELFT>::writeTo(uint8_t *buf) {
   // is to make results easier to read.
   if (sort) {
     const RelType relativeRel = target->relativeRel;
-    parallelSort(relocs, [&](const DynamicReloc &a, const DynamicReloc &b) {
-      return std::make_tuple(a.type != relativeRel, a.r_sym, a.r_offset) <
-             std::make_tuple(b.type != relativeRel, b.r_sym, b.r_offset);
+    auto nonRelative =
+        std::stable_partition(relocs.begin(), relocs.end(),
+                              [=](auto &r) { return r.type == relativeRel; });
+    parallelSort(relocs.begin(), nonRelative,
+                 [&](auto &a, auto &b) { return a.r_offset < b.r_offset; });
+    // Non-relative relocations are few, so don't bother with parallelSort.
+    std::sort(nonRelative, relocs.end(), [&](auto &a, auto &b) {
+      return std::tie(a.r_sym, a.r_offset) < std::tie(b.r_sym, b.r_offset);
     });
   }