[lld][macho] Stop grouping symbols by sections in mapfile.

[Roger]

Summary

As per Bug 50689,

2. getSectionSyms() puts all the symbols into a map of section -> symbols, but this seems unnecessary. This was likely copied from the ELF port, which prints a section header before the list of symbols it contains. But the Mach-O map file doesn't print these headers.

This diff removes getSectionSyms() and keeps all symbols in a flat vector.

What does ld64's mapfile look like?

$ llvm-mc -filetype=obj -triple=x86_64-apple-darwin test.s -o test.o
$ llvm-mc -filetype=obj -triple=x86_64-apple-darwin foo.s -o foo.o
$ ld -map map test.o foo.o -o out -L/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/lib -lSystem

# Path: out
# Arch: x86_64
# Object files:
[  0] linker synthesized
[  1] test.o
[  2] foo.o
# Sections:
# Address       Size            Segment Section
0x100003FB7     0x00000001      __TEXT  __text
0x100003FB8     0x00000000      __TEXT  obj
0x100003FB8     0x00000048      __TEXT  __unwind_info
0x100004000     0x00000001      __DATA  __common
# Symbols:
# Address       Size            File  Name
0x100003FB7     0x00000001      [  1] _main
0x100003FB8     0x00000000      [  2] _foo
0x100003FB8     0x00000048      [  0] compact unwind info
0x100004000     0x00000001      [  1] _number

Perf numbers when linking chromium framework on a 16-Core Intel Xeon W Mac Pro:

base           diff           difference (95% CI)
sys_time   1.406 ± 0.020  1.388 ± 0.019  [  -1.9% ..   -0.6%]
user_time  5.557 ± 0.023  5.914 ± 0.020  [  +6.2% ..   +6.6%]
wall_time  4.455 ± 0.041  4.436 ± 0.035  [  -0.8% ..   -0.0%]
samples    35             35

[Roger]

Deleted unnecessary function.

[Roger]

Remove unnecessary using statement.

[Roger]

Update diff name

[Roger]

Update diff details.

[Roger]

Small fixes.

[Roger]

smal fix.

[Roger]

Compilation fix.

[Roger]

test passes

[int3]

lld/test/MachO/map-file.s

49–51 ↗

(On Diff #396048)

hmm why did the ordering change? and what does ld64 output here?

[Roger]

lld/test/MachO/map-file.s

49–51 ↗

(On Diff #396048)

Since we are no longer grouping symbols by their sections, the order in which they appear will change. I updated the description to include what ld64's mapfile looks like for this example. Aside from the "compact unwind info" that ld64 has that lld does not, the ordering is the same. WDYT?

[MaskRay]

Drive-by: the ELF -Map way has the nice property that it is easy to know the relative section of a symbol. The ld64 way, while there is a separate Symbol part, may provide less information (the information can mostly be inferred from llvm-objdump -t)...

[int3]

@MaskRay makes sense, but I think it's more important that we can act as a drop-in replacement for ld64. We can certainly add support for a different mapfile format in the future.

lld/test/MachO/map-file.s

49–51 ↗

(On Diff #396048)

oh so this makes us more correct then -- excellent!

[Roger]

@int3 could you submit this for me? thanks :)

[oontvoo]

In D114735#3225835, @Roger wrote:

@int3 could you submit this for me? thanks :)

do you still need help landing this?

[Roger]

In D114735#3232598, @oontvoo wrote:

In D114735#3225835, @Roger wrote:

@int3 could you submit this for me? thanks :)

do you still need help landing this?

no, @int3 suggested offline that I benchmark this before submitting so we'll submit after that. Thanks for checking :)

[int3]

So benchmarking instructions... first, download the zipfile in comment #1 on https://bugs.llvm.org/show_bug.cgi?id=48657 and unpack it into a chromium_framework directory. That will serve as our benchmark. Then install cbdr per the instructions here: https://github.com/asayers/cbdr/blob/master/cbdr.md

Now create two builds of LLD, before and after this change. Say the LLD binary before this change is at ~/before/ld64.lld and the one after the change is at ~/after/ld64.lld. Then run the following command from within chromium_framework:

cbdr sample "base:~/before/ld64.lld @response.txt -map beforemap.txt" "diff:~/after/ld64.lld @response.txt -map aftermap.txt" --timeout=300s | tee results.csv | cbdr analyze -s 95

To reduce noise, close as many other processes as possible before kicking off the benchmark. If your readings are still very noisy, try increasing the timeout value in the benchmarking command to get a more precise confidence interval.

So the command above will measure the change in overall LLD runtime. However, since we are running writeMapFile in parallel with other linker work, we should be able to get a more precise estimate of perf improvement by measuring the change in the time it takes to run that function alone. We can collect & extract that data via the --time-trace flag:

#-- bench.sh
RESULT=$(~/${1}/ld64.lld @response.txt -map ${1}map.txt --time-trace-file=${1}trace.txt && cat ${1}trace.txt | python -m json.tool | grep '\"Write map file' -B1 | grep '[0-9]\+' -o)
echo {\"time\":$RESULT}

I used the script as follows:

cbdr sample --bench ~/bench.sh --timeout=300s -- before after

LMK if you have any issues getting this to work :)

[Roger]

$ cbdr sample "base:/tmp/before/ld64.lld @response.txt -map beforemap.txt" "diff:/tmp/after/ld64.lld @response.txt -map aftermap.txt" --timeout=300s | tee results.csv | cbdr analyze -s 95                                                                                           Warming up base...
Warming up diff...
base           diff           difference (95% CI)
sys_time   1.406 ± 0.020  1.388 ± 0.019  [  -1.9% ..   -0.6%]
user_time  5.557 ± 0.023  5.914 ± 0.020  [  +6.2% ..   +6.6%]
wall_time  4.455 ± 0.041  4.436 ± 0.035  [  -0.8% ..   -0.0%]
samples    35             35

lld/MachO/MapFile.cpp

 #include "llvm/Support/Parallel.h"
 #include "llvm/Support/TimeProfiler.h"
 
 using namespace llvm;
 using namespace llvm::sys;
 using namespace lld;
 using namespace lld::macho;
 
-using SymbolMapTy = DenseMap<const InputSection *, SmallVector<Defined *, 4>>;
-
-// Returns a map from sections to their symbols.
-static SymbolMapTy getSectionSyms(ArrayRef<Defined *> syms) {
-  SymbolMapTy ret;
-  for (Defined *dr : syms)
-    ret[dr->isec].push_back(dr);
-
-  // Sort symbols by address. We want to print out symbols in the order they
-  // appear in the output file rather than the order they appeared in the input
-  // files.
-  for (auto &it : ret)
-    parallelSort(
-        it.second.begin(), it.second.end(), [](Defined *a, Defined *b) {
-          return a->getVA() != b->getVA() ? a->getVA() < b->getVA()
-                                          : a->getName() < b->getName();
-        });
-  return ret;
-}
-
 // Returns a list of all symbols that we want to print out.
 static std::vector<Defined *> getSymbols() {
   std::vector<Defined *> v;
   for (InputFile *file : inputFiles)
     if (isa<ObjFile>(file))
       for (Symbol *sym : file->symbols)
         if (auto *d = dyn_cast_or_null<Defined>(sym))
           if (d->isLive() && d->isec && d->getFile() == file) {
for (InputFile *file : inputFiles) {
     if (isa<ObjFile>(file)) {
       os << format("[%3u] %s\n", fileIndex, file->getName().str().c_str());
       readerToFileOrdinal[file] = fileIndex++;
     }
   }
 
   // Collect symbol info that we want to print out.
   std::vector<Defined *> syms = getSymbols();
-  SymbolMapTy sectionSyms = getSectionSyms(syms);
+  parallelSort(syms.begin(), syms.end(), [](Defined *a, Defined *b) {
+    return a->getVA() != b->getVA() ? a->getVA() < b->getVA()
+                                    : a->getName() < b->getName();
+  });
   DenseMap<Symbol *, std::string> symStr = getSymbolStrings(syms);
 
   // Dump table of sections
   os << "# Sections:\n";
   os << "# Address\tSize    \tSegment\tSection\n";
   for (OutputSegment *seg : outputSegments)
     for (OutputSection *osec : seg->getSections()) {
       if (osec->isHidden())
         continue;
 
       os << format("0x%08llX\t0x%08llX\t%s\t%s\n", osec->addr, osec->getSize(),
                    seg->name.str().c_str(), osec->name.str().c_str());
     }
 
   // Dump table of symbols
   os << "# Symbols:\n";
   os << "# Address\t    File  Name\n";
   for (InputSection *isec : inputSections) {
-    auto symsIt = sectionSyms.find(isec);
-    assert(!shouldOmitFromOutput(isec) || (symsIt == sectionSyms.end()));
-    if (symsIt == sectionSyms.end())
-      continue;
-    for (Symbol *sym : symsIt->second) {
+    for (Symbol *sym : syms) {
       os << format("0x%08llX\t[%3u] %s\n", sym->getVA(),
                    readerToFileOrdinal[sym->getFile()], symStr[sym].c_str());
     }
   }
 
   // TODO: when we implement -dead_strip, we should dump dead stripped symbols
 }