[ELF] OrderPass : Order atoms only by ordinals.

Move the init array/fini array sorting to the Output ELF writer.

AFAIK, this is only needed by the X86_64/ARM ABI.

This shaves time taken to self host lld by 0.2 seconds.

Before patch
----------------
4791.062059 task-clock                #    1.634 CPUs utilized            ( +-  0.28% )
     61,107 context-switches          #    0.013 M/sec                    ( +-  0.56% )
2.932902671 seconds time elapsed                                          ( +-  0.84% )

After patch
-------------
4608.417248 task-clock                #    1.669 CPUs utilized            ( +-  0.30% )
     61,616 context-switches          #    0.013 M/sec                    ( +-  0.63% )
2.761012703 seconds time elapsed                                          ( +-  0.63% )

llvm-svn: 232866

4 files changed, 66 insertions, 48 deletions

diff --git a/lld/lib/ReaderWriter/ELF/DefaultLayout.h b/lld/lib/ReaderWriter/ELF/DefaultLayout.h
index 05c7cddc66a..de03ce1cb60 100644
--- a/lld/lib/ReaderWriter/ELF/DefaultLayout.h
+++ b/lld/lib/ReaderWriter/ELF/DefaultLayout.h
@@ -316,13 +316,25 @@ public:
     return _copiedDynSymNames.count(sla->name());
   }
 
+  /// \brief Handle SORT_BY_PRIORITY.
+  void sortOutputSectionByPriority(StringRef outputSectionName,
+                                   StringRef prefix);
+
 protected:
+  /// \brief TargetLayouts may use these functions to reorder the input sections
+  /// in a order defined by their ABI.
+  virtual void finalizeOutputSectionLayout() {}
+
   /// \brief Allocate a new section.
   virtual AtomSection<ELFT> *createSection(
       StringRef name, int32_t contentType,
       DefinedAtom::ContentPermissions contentPermissions,
       SectionOrder sectionOrder);
 
+private:
+  /// Helper function that returns the priority value from an input section.
+  uint32_t getPriorityFromSectionName(StringRef sectionName) const;
+
 protected:
   llvm::BumpPtrAllocator _allocator;
   SectionMapT _sectionMap;
@@ -657,13 +669,56 @@ template <class ELFT> void DefaultLayout<ELFT>::createOutputSections() {
   }
 }
 
+template <class ELFT>
+uint32_t
+DefaultLayout<ELFT>::getPriorityFromSectionName(StringRef sectionName) const {
+  StringRef priority = sectionName.drop_front().rsplit('.').second;
+  uint32_t prio;
+  if (priority.getAsInteger(10, prio))
+    return std::numeric_limits<uint32_t>::max();
+  return prio;
+}
+
+template <class ELFT>
+void DefaultLayout<ELFT>::sortOutputSectionByPriority(
+    StringRef outputSectionName, StringRef prefix) {
+  OutputSection<ELFT> *outputSection = findOutputSection(outputSectionName);
+  if (!outputSection)
+    return;
+
+  auto sections = outputSection->sections();
+
+  std::sort(sections.begin(), sections.end(),
+            [&](Chunk<ELFT> *lhs, Chunk<ELFT> *rhs) {
+              Section<ELFT> *lhsSection = dyn_cast<Section<ELFT>>(lhs);
+              Section<ELFT> *rhsSection = dyn_cast<Section<ELFT>>(rhs);
+              if (!lhsSection || !rhsSection)
+                return false;
+              StringRef lhsSectionName = lhsSection->inputSectionName();
+              StringRef rhsSectionName = rhsSection->inputSectionName();
+
+              if (!prefix.empty()) {
+                if (!lhsSectionName.startswith(prefix) ||
+                    !rhsSectionName.startswith(prefix))
+                  return false;
+              }
+              return getPriorityFromSectionName(lhsSectionName) <
+                     getPriorityFromSectionName(rhsSectionName);
+            });
+};
+
 template <class ELFT> void DefaultLayout<ELFT>::assignSectionsToSegments() {
   ScopedTask task(getDefaultDomain(), "assignSectionsToSegments");
   ELFLinkingContext::OutputMagic outputMagic = _context.getOutputMagic();
   // sort the sections by their order as defined by the layout
   sortInputSections();
+
   // Create output sections.
   createOutputSections();
+
+  // Finalize output section layout.
+  finalizeOutputSectionLayout();
+
   // Set the ordinal after sorting the sections
   int ordinal = 1;
   for (auto osi : _outputSections) {
diff --git a/lld/lib/ReaderWriter/ELF/OrderPass.h b/lld/lib/ReaderWriter/ELF/OrderPass.h
index 0948485c7bf..d126b830db9 100644
--- a/lld/lib/ReaderWriter/ELF/OrderPass.h
+++ b/lld/lib/ReaderWriter/ELF/OrderPass.h
@@ -17,49 +17,13 @@ namespace lld {
 namespace elf {
 
 /// \brief This pass sorts atoms by file and atom ordinals.
-/// .{init,fini}_array.<priority> sections are handled specially.
 class OrderPass : public Pass {
 public:
   void perform(std::unique_ptr<MutableFile> &file) override {
-    MutableFile::DefinedAtomRange defined = file->definedAtoms();
-    auto last = std::partition(defined.begin(), defined.end(), isInitFini);
-    parallel_sort(defined.begin(), last, compareInitFini);
-    parallel_sort(last, defined.end(), DefinedAtom::compareByPosition);
-  }
-
-private:
-  static bool isInitFini(const DefinedAtom *atom) {
-    if (atom->sectionChoice() != DefinedAtom::sectionCustomRequired)
-      return false;
-    StringRef name = atom->customSectionName();
-    return name.startswith(".init_array") || name.startswith(".fini_array");
-  }
-
-  // Parses the number in .{init,fini}_array.<number>.
-  // Returns UINT32_MAX by default.
-  static uint32_t getPriority(const DefinedAtom *atom) {
-    StringRef sec = atom->customSectionName();
-    StringRef num = sec.drop_front().rsplit('.').second;
-    uint32_t prio;
-    if (num.getAsInteger(10, prio))
-      return std::numeric_limits<uint32_t>::max();
-    return prio;
-  }
-
-  static bool compareInitFini(const DefinedAtom *lhs, const DefinedAtom *rhs) {
-    // Sort {.init_array, .fini_array}[.<num>] sections
-    // according to their number. Sections without optional
-    // numer suffix should go last.
-    uint32_t lp = getPriority(lhs);
-    uint32_t rp = getPriority(rhs);
-    if (lp != rp)
-      return lp < rp;
-
-    // If both atoms have the same priority, fall back to default.
-    return DefinedAtom::compareByPosition(lhs, rhs);
+    parallel_sort(file->definedAtoms().begin(), file->definedAtoms().end(),
+                  DefinedAtom::compareByPosition);
   }
 };
-
 }
 }
 
diff --git a/lld/lib/ReaderWriter/ELF/X86_64/X86_64TargetHandler.h b/lld/lib/ReaderWriter/ELF/X86_64/X86_64TargetHandler.h
index 24cdd9850c4..57da7bca01e 100644
--- a/lld/lib/ReaderWriter/ELF/X86_64/X86_64TargetHandler.h
+++ b/lld/lib/ReaderWriter/ELF/X86_64/X86_64TargetHandler.h
@@ -24,6 +24,11 @@ class X86_64TargetLayout : public TargetLayout<X86_64ELFType> {
 public:
   X86_64TargetLayout(X86_64LinkingContext &context)
       : TargetLayout(context) {}
+
+  void finalizeOutputSectionLayout() override {
+    sortOutputSectionByPriority(".init_array", ".init_array");
+    sortOutputSectionByPriority(".fini_array", ".fini_array");
+  }
 };
 
 class X86_64TargetHandler
diff --git a/lld/test/elf/init_array-order.test b/lld/test/elf/init_array-order.test
index 1ebb24bac22..b57b3807b69 100644
--- a/lld/test/elf/init_array-order.test
+++ b/lld/test/elf/init_array-order.test
@@ -1,6 +1,7 @@
 #RUN: yaml2obj -format=elf %s > %t
 #RUN: lld -flavor gnu -target x86_64-linux %t --noinhibit-exec \
-#RUN:   --output-filetype=yaml | FileCheck %s
+#RUN:   -o %t1.out
+#RUN: llvm-objdump -s %t1.out | FileCheck %s
 
 !ELF
 FileHeader:
@@ -62,12 +63,5 @@ Symbols:
     Type: STT_SECTION
     Section: .init_array
 
-#CHECK: defined-atoms:
-#CHECK:   content: [ 01,
-#CHECK:   section-name: .init_array.1
-#CHECK:   content: [ 02,
-#CHECK:   section-name: .init_array.2
-#CHECK:   content: [ 03,
-#CHECK:   section-name: .init_array.3
-#CHECK:   content: [ 99,
-#CHECK:   section-name: .init_array
+#CHECK:  {{[0xa-f0-9]+}} 01000000 00000000 02000000 00000000
+#CHECK:  {{[0xa-f0-9]+}} 03000000 00000000 99000000 00000000