[lld-macho][nfc] Sort OutputSections based on explicit order of command-line inputs

[int3]

Summary

This diff paves the way for D102964: [lld-macho] Implement cstring deduplication which adds a new kind of
InputSection.

We previously maintained section ordering implicitly: we created
InputSections as we parsed each file in command-line order, and passed
on this ordering when we created OutputSections and OutputSegments by
iterating over these InputSections. The implicitness of the ordering
made it difficult to refactor the code to e.g. handle a new type of
InputSection. As such, I've codified the ordering explicitly via
inputOrder fields. This also allows us to use sort instead of
stable_sort.

Benchmarking chromium_framework on my 3.2 GHz 16-Core Intel Xeon W:

    N           Min           Max        Median           Avg        Stddev
x  20          4.23          4.35          4.27         4.274   0.030157481
+  20          4.24          4.38          4.27        4.2815   0.033759989
No difference proven at 95.0% confidence

[alexander-shaposhnikov]

lld/MachO/OutputSegment.h

56

this looks a bit strange that inputOrder is size_t but the function below (sectionOrder) returns int

[int3]

lld/MachO/OutputSegment.h

56

well the values here are generated from an index into a vector, but I see your point

[int3]

use int

[alexander-shaposhnikov]

lld/MachO/OutputSegment.h

47

the presence of comparator and inputOrder, perhaps, deserves some comments
(e.g. are there any places where sections are sorted using different comparators ?)
otherwise this probably can be simplified a bit.

[int3]

lld/MachO/OutputSegment.h

47

There's only one comparator... I think this only exists so that all the segment+section sorting code could live together in Writer.cpp. But yeah we can simplify it by moving all the sorting code into OutputSegment.cpp instead. Out of scope for this diff though

[int3]

lld/MachO/OutputSegment.h

47

D102974: [lld-macho][nfc] Remove unnecessary parameterization of section sort

[thakis]

lld/MachO/OutputSection.h

64

This is a dangerous default that is almost always wrong in practice since it makes every section compete with BSS sections (which _must_ be last). See https://bugs.llvm.org/show_bug.cgi?id=50769#c5

lld/MachO/OutputSection.h

 //===- OutputSection.h ------------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_MACHO_OUTPUT_SECTION_H
 #define LLD_MACHO_OUTPUT_SECTION_H
 
 #include "lld/Common/LLVM.h"
 #include "llvm/ADT/DenseMap.h"
 
+#include <limits>
+
 namespace lld {
 namespace macho {
 
 class InputSection;
 class OutputSegment;
 
 // Output sections represent the finalized sections present within the final
 // linked executable. They can represent special sections (like the symbol
virtual void finalize() {
     // TODO investigate refactoring synthetic section finalization logic into
     // overrides of this function.
   }
 
   virtual void writeTo(uint8_t *buf) const = 0;
 
   StringRef name;
   OutputSegment *parent = nullptr;
+  // For output sections that don't have explicit ordering requirements, their
+  // output order should be based on the order of the input sections they
+  // contain.
+  size_t inputOrder = std::numeric_limits<size_t>::max();
 
   uint32_t index = 0;
   uint64_t addr = 0;
   uint64_t fileOff = 0;
   uint32_t align = 1;
   uint32_t flags = 0;
   uint32_t reserved1 = 0;
   uint32_t reserved2 = 0;

lld/MachO/OutputSegment.h

 //===- OutputSegment.h ------------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_MACHO_OUTPUT_SEGMENT_H
 #define LLD_MACHO_OUTPUT_SEGMENT_H
 
 #include "OutputSection.h"
 #include "lld/Common/LLVM.h"
 
+#include <limits>
+
 namespace lld {
 namespace macho {
 
 namespace segment_names {
 
 constexpr const char dataConst[] = "__DATA_CONST";
 constexpr const char dataDirty[] = "__DATA_DIRTY";
 constexpr const char data[] = "__DATA";

 class OutputSegment {
 public:
   const OutputSection *firstSection() const { return sections.front(); }
   const OutputSection *lastSection() const { return sections.back(); }
 
   void addOutputSection(OutputSection *os);
   void sortOutputSections(
       llvm::function_ref<bool(OutputSection *, OutputSection *)> comparator) {
-    llvm::stable_sort(sections, comparator);
+    llvm::sort(sections, comparator);
   }
 
   const std::vector<OutputSection *> &getSections() const { return sections; }
   size_t numNonHiddenSections() const;
 
   uint64_t fileOff = 0;
   uint64_t fileSize = 0;
   uint64_t vmSize = 0;
+  size_t inputOrder = std::numeric_limits<size_t>::max();
   StringRef name;
   uint32_t maxProt = 0;
   uint32_t initProt = 0;
   uint8_t index;
 
 private:
   std::vector<OutputSection *> sections;
 };

lld/MachO/OutputSegment.cpp

 size_t OutputSegment::numNonHiddenSections() const {
   size_t count = 0;
   for (const OutputSection *osec : sections)
     count += (!osec->isHidden() ? 1 : 0);
   return count;
 }
 
 void OutputSegment::addOutputSection(OutputSection *osec) {
+  inputOrder = std::min(inputOrder, osec->inputOrder);
+
   osec->parent = this;
   sections.push_back(osec);
 
   for (const SectionAlign &sectAlign : config->sectionAlignments)
     if (sectAlign.segName == name && sectAlign.sectName == osec->name)
       osec->align = sectAlign.align;
 }
 

lld/MachO/Writer.cpp

return StringSwitch<int>(seg->name)
       .Case(segment_names::pageZero, -4)
       .Case(segment_names::text, -3)
       .Case(segment_names::dataConst, -2)
       .Case(segment_names::data, -1)
       .Case(segment_names::llvm, std::numeric_limits<int>::max() - 1)
       // Make sure __LINKEDIT is the last segment (i.e. all its hidden
       // sections must be ordered after other sections).
       .Case(segment_names::linkEdit, std::numeric_limits<int>::max())
-      .Default(0);
+      .Default(seg->inputOrder);
 }
 
 static int sectionOrder(OutputSection *osec) {
   StringRef segname = osec->parent->name;
   // Sections are uniquely identified by their segment + section name.
   if (segname == segment_names::text) {
     return StringSwitch<int>(osec->name)
         .Case(section_names::header, -4)
         .Case(section_names::text, -3)
         .Case(section_names::stubs, -2)
         .Case(section_names::stubHelper, -1)
         .Case(section_names::unwindInfo, std::numeric_limits<int>::max() - 1)
         .Case(section_names::ehFrame, std::numeric_limits<int>::max())
-        .Default(0);
+        .Default(osec->inputOrder);
   } else if (segname == segment_names::data ||
              segname == segment_names::dataConst) {
     // For each thread spawned, dyld will initialize its TLVs by copying the
     // address range from the start of the first thread-local data section to
     // the end of the last one. We therefore arrange these sections contiguously
     // to minimize the amount of memory used. Additionally, since zerofill
     // sections must be at the end of their segments, and since TLV data
     // sections can be zerofills, we end up putting all TLV data sections at the
     // end of the segment.
     switch (sectionType(osec->flags)) {
     case S_THREAD_LOCAL_REGULAR:
       return std::numeric_limits<int>::max() - 2;
     case S_THREAD_LOCAL_ZEROFILL:
       return std::numeric_limits<int>::max() - 1;
     case S_ZEROFILL:
       return std::numeric_limits<int>::max();
     default:
       return StringSwitch<int>(osec->name)
+          .Case(section_names::got, -3)
           .Case(section_names::lazySymbolPtr, -2)
-          .Case(section_names::data, -1)
-          .Default(0);
+          .Case(section_names::const_, -1)
+          .Default(osec->inputOrder);
     }
   } else if (segname == segment_names::linkEdit) {
     return StringSwitch<int>(osec->name)
         .Case(section_names::rebase, -9)
         .Case(section_names::binding, -8)
         .Case(section_names::weakBinding, -7)
         .Case(section_names::lazyBinding, -6)
         .Case(section_names::export_, -5)
         .Case(section_names::functionStarts, -4)
         .Case(section_names::symbolTable, -3)
         .Case(section_names::indirectSymbolTable, -2)
         .Case(section_names::stringTable, -1)
         .Case(section_names::codeSignature, std::numeric_limits<int>::max())
-        .Default(0);
+        .Default(osec->inputOrder);
   }
   // ZeroFill sections must always be the at the end of their segments,
   // otherwise subsequent sections may get overwritten with zeroes at runtime.
   if (sectionType(osec->flags) == S_ZEROFILL)
     return std::numeric_limits<int>::max();
-  return 0;
+  return osec->inputOrder;
 }
 
 template <typename T, typename F>
 static std::function<bool(T, T)> compareByOrder(F ord) {
   return [=](T a, T b) { return ord(a) < ord(b); };
 }
 
 // Sorting only can happen once all outputs have been collected. Here we sort
 // segments, output sections within each segment, and input sections within each
 // output segment.
 static void sortSegmentsAndSections() {
   TimeTraceScope timeScope("Sort segments and sections");
 
-  llvm::stable_sort(outputSegments,
-                    compareByOrder<OutputSegment *>(segmentOrder));
+  llvm::sort(outputSegments, compareByOrder<OutputSegment *>(segmentOrder));
 
   DenseMap<const InputSection *, size_t> isecPriorities =
       buildInputSectionPriorities();
 
   uint32_t sectionIndex = 0;
   for (OutputSegment *seg : outputSegments) {
     seg->sortOutputSections(compareByOrder<OutputSection *>(sectionOrder));
     for (OutputSection *osec : seg->getSections()) {
template <class LP> void Writer::createOutputSections() {
   case MH_DYLIB:
   case MH_BUNDLE:
     break;
   default:
     llvm_unreachable("unhandled output file type");
   }
 
   // Then add input sections to output sections.
-  MapVector<NamePair, ConcatOutputSection *> concatOutputSections;
-  for (InputSection *isec : inputSections) {
+  DenseMap<NamePair, ConcatOutputSection *> concatOutputSections;
+  for (const auto &p : enumerate(inputSections)) {
+    InputSection *isec = p.value();
     if (isec->shouldOmitFromOutput())
       continue;
     NamePair names = maybeRenameSection({isec->segname, isec->name});
     ConcatOutputSection *&osec = concatOutputSections[names];
-    if (osec == nullptr)
+    if (osec == nullptr) {
       osec = make<ConcatOutputSection>(names.second);
+      osec->inputOrder = p.index();
+    }
     osec->addInput(isec);
   }
 
   for (const auto &it : concatOutputSections) {
     StringRef segname = it.first.first;
     ConcatOutputSection *osec = it.second;
     if (segname == segment_names::ld) {
       assert(osec->name == section_names::compactUnwind);

lld/test/MachO/load-command-sequence.s

 # COMMON: cmd LC_SEGMENT_64
 # COMMON: segname __TEXT
 # COMMON: sectname __text
 # COMMON: segname __TEXT
 # COMMON: sectname __cstring
 # COMMON: segname __TEXT
 # COMMON: cmd LC_SEGMENT_64
 # COMMON: segname __DATA_CONST
-# COMMON: sectname __const
-# COMMON: segname __DATA_CONST
 # COMMON: sectname __got
 # COMMON: segname __DATA_CONST
+# COMMON: sectname __const
+# COMMON: segname __DATA_CONST
 # COMMON: cmd LC_SEGMENT_64
 # COMMON: segname __DATA
 # COMMON: sectname __data
 # COMMON: segname __DATA
 # COMMON: cmd LC_SEGMENT_64
 # COMMON: segname __LINKEDIT
 # COMMON: cmd LC_DYLD_INFO_ONLY
 # COMMON: cmd LC_SYMTAB

lld/test/MachO/section-order.s

+# REQUIRES: x86
+## Check that section ordering follows from input file ordering.
+# RUN: rm -rf %t; split-file %s %t
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/1.s -o %t/1.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/2.s -o %t/2.o
+# RUN: %lld -dylib %t/1.o %t/2.o -o %t/12
+# RUN: %lld -dylib %t/2.o %t/1.o -o %t/21
+# RUN: llvm-objdump --macho --section-headers %t/12 | FileCheck %s --check-prefix=CHECK-12
+# RUN: llvm-objdump --macho --section-headers %t/21 | FileCheck %s --check-prefix=CHECK-21
+
+# CHECK-12:      __text
+# CHECK-12-NEXT: foo
+# CHECK-12-NEXT: bar
+# CHECK-12-NEXT: __cstring
+
+# CHECK-21:      __text
+# CHECK-21-NEXT: __cstring
+# CHECK-21-NEXT: bar
+# CHECK-21-NEXT: foo
+
+#--- 1.s
+.section __TEXT,foo
+  .space 1
+.section __TEXT,bar
+  .space 1
+.cstring
+  .asciz ""
+
+#--- 2.s
+.cstring
+  .asciz ""
+.section __TEXT,bar
+  .space 1
+.section __TEXT,foo
+  .space 1

lld/test/MachO/weak-binding.s

 # REQUIRES: x86
 # RUN: rm -rf %t; split-file %s %t
 # RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/test.s -o %t/test.o
 # RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/libfoo.s -o %t/libfoo.o
 # RUN: %lld -dylib %t/libfoo.o -o %t/libfoo.dylib
 # RUN: %lld %t/test.o -L%t -lfoo -o %t/test -lSystem
-# RUN: llvm-objdump -d --no-show-raw-insn --rebase --bind --lazy-bind --weak-bind --full-contents %t/test | \
-# RUN:   FileCheck %s
+# RUN: llvm-objdump -d --no-show-raw-insn --rebase --bind --lazy-bind \
+# RUN:   --weak-bind --full-contents %t/test | FileCheck %s
 
 # CHECK:      Contents of section __DATA_CONST,__got:
 ## Check that this section contains a nonzero pointer. It should point to
 ## _weak_external_for_gotpcrel.
 # CHECK-NEXT: {{[0-9a-f]+}} {{[0-9a-f ]*[1-9a-f]+[0-9a-f ]*}}
 
 # CHECK:      Contents of section __DATA,__la_symbol_ptr:
 ## Check that this section contains a nonzero pointer. It should point to

 # CHECK-LABEL: Rebase table:
 # CHECK:       __DATA        __la_symbol_ptr 0x[[#%x,WEAK_EXT_FN:]]  pointer
 
 # CHECK-LABEL: Bind table:
 # CHECK-DAG:   __DATA_CONST  __got           0x[[#WEAK_DY_GOT_ADDR]] pointer 0 libfoo    _weak_dysym_for_gotpcrel
 # CHECK-DAG:   __DATA        __la_symbol_ptr 0x[[#%x,WEAK_DY_FN:]]   pointer 0 libfoo    _weak_dysym_fn
 # CHECK-DAG:   __DATA        __data          0x[[#%x,WEAK_DY:]]      pointer 0 libfoo    _weak_dysym
 # CHECK-DAG:   __DATA        __thread_vars   0x{{[0-9a-f]*}}         pointer 0 libSystem __tlv_bootstrap
+# CHECK-DAG:   __DATA        __thread_vars   0x{{[0-9a-f]*}}         pointer 0 libSystem __tlv_bootstrap
 # CHECK-DAG:   __DATA        __thread_ptrs   0x[[#WEAK_DY_TLV_ADDR]] pointer 0 libfoo    _weak_dysym_tlv
 ## Check that we don't have any other bindings
-# CHECK-NOT:   pointer
+# CHECK-EMPTY:
 
 # CHECK-LABEL: Lazy bind table:
+# CHECK-NEXT:  segment section address dylib symbol
 ## Verify that we have no lazy bindings
-# CHECK-NOT:   pointer
+# CHECK-EMPTY:
 
 # CHECK-LABEL: Weak bind table:
 # CHECK-DAG:   __DATA_CONST __got           0x[[#WEAK_DY_GOT_ADDR]]   pointer 0 _weak_dysym_for_gotpcrel
 # CHECK-DAG:   __DATA_CONST __got           0x[[#WEAK_EXT_GOT_ADDR]]  pointer 0 _weak_external_for_gotpcrel
 # CHECK-DAG:   __DATA       __data          0x[[#WEAK_DY]]            pointer 0 _weak_dysym
 # CHECK-DAG:   __DATA       __thread_ptrs   0x[[#WEAK_TLV_ADDR]]      pointer 0 _weak_tlv
 # CHECK-DAG:   __DATA       __thread_ptrs   0x[[#WEAK_DY_TLV_ADDR]]   pointer 0 _weak_dysym_tlv
 # CHECK-DAG:   __DATA       __data          0x{{[0-9a-f]*}}           pointer 2 _weak_external
 # CHECK-DAG:   __DATA       __la_symbol_ptr 0x[[#WEAK_DY_FN]]         pointer 0 _weak_dysym_fn
 # CHECK-DAG:   __DATA       __la_symbol_ptr 0x[[#WEAK_EXT_FN]]        pointer 0 _weak_external_fn
 ## Check that we don't have any other bindings
-# CHECK-NOT:   pointer
+# CHECK-EMPTY:
 
 ## Weak internal symbols don't get bindings
 # RUN: llvm-objdump --macho --bind --lazy-bind --weak-bind %t/test | FileCheck %s --check-prefix=WEAK-INTERNAL
 # WEAK-INTERNAL-NOT: _weak_internal
 # WEAK-INTERNAL-NOT: _weak_internal_fn
 # WEAK-INTERNAL-NOT: _weak_internal_tlv
 
 #--- libfoo.s