[lld/mac] Fix nondeterminism in output section ordering

[thakis]

Summary

The two different thread_local_regular sections (__thread_data and
more_thread_data) had nondeterminstic ordering for two reasons:

1. https://reviews.llvm.org/D102972 changed concatOutputSections from MapVector to DenseMap, so when we iterate it to make output segments, we would add the two sections to the __DATA output segment in nondeterministic order.

2. The same change also moved the two stable_sort()s for segments and sections to sort(). Since sections with assigned priority (such as TLV data) have the same priority for all sections, this is incorrect -- we must use stable_sort() so that the initial (input-order-based) order remains.

As a side effect, we now (deterministically) put the common
section in front of bss (while previously we happened to
put it after it). (common and bss are both zerofill so
both have order INT_MAX, but common symbols are added to
inputSections before normal sections are collected.)

Makes lld/test/MachO/tlv.s and lld/test/MachO/tlv-dylib.s pass with
LLVM_ENABLE_EXPENSIVE_CHECKS=ON.

[tschuett]

lld/MachO/OutputSegment.cpp

143

Do you want to add a comment here: it has to be stable_sort ...

lld/MachO/Writer.cpp

81

Do you want to add a comment here: The order of bla has to be deterministic or whatever.

[thakis]

comments, tlv-dylib.s

[int3]

D'oh, sorry about that, and thanks for the fix!

[MaskRay]

Make lld/test/MachO/tlv.s,tlv-dylib.s pass with expensive tests

I think the subject needs to mention that it fixes a non-determinism, otherwise people might think this just adjusts fragile tests.

[thakis]

In D105054#2845535, @MaskRay wrote:

Make lld/test/MachO/tlv.s,tlv-dylib.s pass with expensive tests

I think the subject needs to mention that it fixes a non-determinism, otherwise people might think this just adjusts fragile tests.

Good point, done.

lld/MachO/OutputSegment.cpp

static int sectionOrder(OutputSection *osec) {
   // size to detect if a segment has zerofill sections, and if so it maps
   // the missing tail as zerofill.
   if (sectionType(osec->flags) == S_ZEROFILL)
     return std::numeric_limits<int>::max();
   return osec->inputOrder;
 }
 
 void OutputSegment::sortOutputSections() {
-  llvm::sort(sections, compareByOrder<OutputSection *>(sectionOrder));
+  llvm::stable_sort(sections, compareByOrder<OutputSection *>(sectionOrder));
 }
 
 void macho::sortOutputSegments() {
+  // sort() instead of stable_sort() is fine because segmentOrder() is
+  // name-based and getOrCreateOutputSegment() makes there's only a single
+  // segment for every name.
   llvm::sort(outputSegments, compareByOrder<OutputSegment *>(segmentOrder));
 }
 
 static DenseMap<StringRef, OutputSegment *> nameToOutputSegment;
 std::vector<OutputSegment *> macho::outputSegments;
 
 OutputSegment *macho::getOrCreateOutputSegment(StringRef name) {
   OutputSegment *&segRef = nameToOutputSegment[name];

lld/MachO/Writer.cpp

public:
   SymtabSection *symtabSection = nullptr;
   IndirectSymtabSection *indirectSymtabSection = nullptr;
   CodeSignatureSection *codeSignatureSection = nullptr;
   DataInCodeSection *dataInCodeSection = nullptr;
   FunctionStartsSection *functionStartsSection = nullptr;
 
   LCUuid *uuidCommand = nullptr;
   OutputSegment *linkEditSegment = nullptr;
-  DenseMap<NamePair, ConcatOutputSection *> concatOutputSections;
+  MapVector<NamePair, ConcatOutputSection *> concatOutputSections;
 };
 
 // LC_DYLD_INFO_ONLY stores the offsets of symbol import/export information.
 class LCDyldInfo final : public LoadCommand {
 public:
   LCDyldInfo(RebaseSection *rebaseSection, BindingSection *bindingSection,
              WeakBindingSection *weakBindingSection,
              LazyBindingSection *lazyBindingSection,