[lld/mac] Make symbol table order deterministic

[thakis]

Summary

SymtabSection::emitStabs() writes the symbol table in the order
of externalSymbols, which has the order of symtab->getSymbols(),
which is just the order symbols are added to the symbol table.

In practice, symbols in the symbol files of input .o files are
sorted, but since that's not guaranteed we sort them in
ObjFile::parseSymbols(). To make sure several symbols with the same
address keep the order they're in the input file, we have to use
stable_sort().

In practice, std::sort() on already-sorted inputs won't change the order
of just adjacent elements, and while in theory std::sort() could use a
random pivot, in practice the code should be deterministic as it was
previously too.

But now lld/test/MachO/stabs.s passes with LLVM_ENABLE_EXPENSIVE_CHECKS=ON
(the last test that was failing with that set).

Fixes a regression from D99972.

While here, remove an empty section in stabs.s and move
.subsections_via_symbols to the end where it usually is (this part no
behavior change).

[int3]

Thanks! Would be nice to have LLVM_ENABLE_EXPENSIVE_CHECKS=ON running as part of some buildbot...

[thakis]

Thanks!

In D105071#2846061, @int3 wrote:

Would be nice to have LLVM_ENABLE_EXPENSIVE_CHECKS=ON running as part of some buildbot...

Agreed. Looks like there are bots with expensive checks enabled here:
https://lab.llvm.org/buildbot/#/builders/16
https://lab.llvm.org/buildbot/#/builders/104

But they only -DLLVM_ENABLE_PROJECTS=llvm, not lld. Maybe we can figure out who owns them and ask them to add lld? …Hm, one of them was added in D69359. @vvereschaka, could we run lld tests on that bot too? lld tests run pretty quickly.

[vvereschaka]

Hi @thakis,

@vvereschaka, could we run lld tests on that bot too? lld tests run pretty quickly.

ok, it shouldn't be a problem. I'll take a look and update the builder configurations accordingly.

[thakis]

In D105071#2847729, @vvereschaka wrote:

Hi @thakis,

@vvereschaka, could we run lld tests on that bot too? lld tests run pretty quickly.

ok, it shouldn't be a problem. I'll take a look and update the builder configurations accordingly.

Thanks! :)

[vvereschaka]

I did some research and I found that lld project does not contain any expensive checks. There is nothing to run on the expensive check builders.
But there is few builders that run the lld tests including MachO/stabs.s. As example lld-x86_64-ubuntu-fast - https://lab.llvm.org/buildbot/#/builders/58

[int3]

I did some research and I found that lld project does not contain any expensive checks.

Maybe I'm misunderstanding, but we did have tests that were failing when configured with -DLLVM_ENABLE_EXPENSIVE_CHECKS=ON. We don't have LLD code that ifdef's on EXPENSIVE_CHECKS, but we use a bunch of LLVM data structures which do

[vvereschaka]

Now I got it, thank you. I have prepared proper changes here https://reviews.llvm.org/D105369

lld/MachO/InputFiles.cpp

void ObjFile::parseSymbols(ArrayRef<typename LP::section> sectionHeaders,
   // Calculate symbol sizes and create subsections by splitting the sections
   // along symbol boundaries.
   for (size_t i = 0; i < subsections.size(); ++i) {
     SubsectionMap &subsecMap = subsections[i];
     if (subsecMap.empty())
       continue;
 
     std::vector<uint32_t> &symbolIndices = symbolsBySection[i];
-    llvm::sort(symbolIndices, [&](uint32_t lhs, uint32_t rhs) {
+    llvm::stable_sort(symbolIndices, [&](uint32_t lhs, uint32_t rhs) {
       return nList[lhs].n_value < nList[rhs].n_value;
     });
     uint64_t sectionAddr = sectionHeaders[i].addr;
     uint32_t sectionAlign = 1u << sectionHeaders[i].align;
 
     // We populate subsecMap by repeatedly splitting the last (highest address)
     // subsection.
     SubsectionEntry subsecEntry = subsecMap.back();

lld/test/MachO/stabs.s

.set Lset1, Lsection_abbrev-Lsection_abbrev ## Offset Into Abbrev. Section
   .byte  1                       ## Abbrev [1] 0xb:0x48 DW_TAG_compile_unit
   .long  0                       ## DW_AT_name
   .long  9                       ## DW_AT_comp_dir
   .quad  Lfunc_begin0            ## DW_AT_low_pc
 .set Lset3, Lfunc_end0-Lfunc_begin0     ## DW_AT_high_pc
   .long  Lset3
   .byte  0                       ## End Of Children Mark
 Ldebug_info_end0:
-.subsections_via_symbols
-.section  __DWARF,__debug_line,regular,debug
 
 .section OTHER,more_text,regular,pure_instructions
 .globl _fun
 _fun:
   ret
 
+.subsections_via_symbols
+
 #--- foo.s
 .text
 .globl  _foo
 _foo:
 Lfunc_begin0:
   retq
 Lfunc_end0:
 
.set Lset1, Lsection_abbrev-Lsection_abbrev ## Offset Into Abbrev. Section
   .byte  1                       ## Abbrev [1] 0xb:0x48 DW_TAG_compile_unit
   .long  0                       ## DW_AT_name
   .long  8                       ## DW_AT_comp_dir
   .quad  Lfunc_begin0            ## DW_AT_low_pc
 .set Lset3, Lfunc_end0-Lfunc_begin0     ## DW_AT_high_pc
   .long  Lset3
   .byte  0                       ## End Of Children Mark
 Ldebug_info_end0:
-.subsections_via_symbols
-.section  __DWARF,__debug_line,regular,debug
 
 .section  __DWARF,__debug_aranges,regular,debug
 ltmp1:
   .byte 0
 
+.subsections_via_symbols
+
 #--- no-debug.s
 ## This file has no debug info.
 .text
 .globl _no_debug
 _no_debug:
   ret