[lld][Macho] Include dead-stripped symbols in mapfile

[Roger]

Summary

ld64 outputs dead stripped symbols when using the -dead-strip flag. This change mimics that behavior for lld.

ld64's -dead_strip flag outputs:

$ ld -map map basics.o -o out -dead_strip -L/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/lib -lSystem
$ cat map
# Path: out
# Arch: x86_64
# Object files:
[  0] linker synthesized
[  1] basics.o
# Sections:
# Address       Size            Segment Section
0x100003F97     0x00000021      __TEXT  __text
0x100003FB8     0x00000048      __TEXT  __unwind_info
0x100004000     0x00000008      __DATA_CONST    __got
0x100008000     0x00000010      __DATA  __ref_section
0x100008010     0x00000001      __DATA  __common
# Symbols:
# Address       Size            File  Name
0x100003F97     0x00000006      [  1] _ref_local
0x100003F9D     0x00000001      [  1] _ref_private_extern
0x100003F9E     0x0000000C      [  1] _main
0x100003FAA     0x00000006      [  1] _no_dead_strip_globl
0x100003FB0     0x00000001      [  1] _ref_from_no_dead_strip_globl
0x100003FB1     0x00000006      [  1] _no_dead_strip_local
0x100003FB7     0x00000001      [  1] _ref_from_no_dead_strip_local
0x100003FB8     0x00000048      [  0] compact unwind info
0x100004000     0x00000008      [  0] non-lazy-pointer-to-local: _ref_com
0x100008000     0x00000008      [  1] _ref_data
0x100008008     0x00000008      [  1] l_ref_data
0x100008010     0x00000001      [  1] _ref_com

# Dead Stripped Symbols:
#               Size            File  Name
<<dead>>        0x00000006      [  1] _unref_extern
<<dead>>        0x00000001      [  1] _unref_local
<<dead>>        0x00000007      [  1] _unref_private_extern
<<dead>>        0x00000001      [  1] _ref_private_extern_u
<<dead>>        0x00000008      [  1] _unref_data
<<dead>>        0x00000008      [  1] l_unref_data
<<dead>>        0x00000001      [  1] _unref_com

[Roger]

Small fixes.

[Roger]

small fix.

[Roger]

Compilation fix.

[Roger]

test passes

[Roger]

Update.

[Roger]

Update

[Roger]

I expect this will need some advice but I think it's ready for its initial review.

[thevinster]

The output from ld64 doesn't look like what lld produces. Also the command you linked above doesn't pass in dead_strip. Is ld64 always outputting dead stripped symbols regardless of the flag or is the summary a typo?

lld/MachO/MapFile.cpp

43

Why do we need to propagate Live to the lambda? Does ld64 order dead stripped symbols by the name only?

44

nit: Variable name should be camel case. Also, I think dumpLive or something around that seems to be better fit than just Live.

[int3]

lld/MachO/MapFile.cpp

44

+1 for camel case. Also, rather than calling getSymbols twice, each time iterating over all symbols, it would be more efficient to have the function output two vectors, one for live and one for dead symbols.

[Roger]

Squashing separate commits.

[Roger]

In D114737#3216825, @thevinster wrote:

The output from ld64 doesn't look like what lld produces.

You're right that the new dead symbol section is not exactly the same as what ld64 outputs. look lld/test/MachO/dead-strip.s. I followed the precedence set by lld's section for live symbols and basically replicated that for dead symbols. Do you think this needs to be changed?

Also the command you linked above doesn't pass in dead_strip. Is ld64 always outputting dead stripped symbols regardless of the flag or is the summary a typo?

Yeah, it was a typo. I fixed the summary.

lld/MachO/MapFile.cpp

43

The ordering for live symbols is first by virtual address and then by name. As I understand, dead-stripped symbols don't have virtual addresses so we can just order by name.

[thevinster]

Do you think this needs to be changed?

I don't think the core logic needs to be changed. It makes more sense to have LLD's output be a subset of ld64 (for now), which hints at the fact that our dead strip isn't on par with ld64 (or something else is going on).

lld/MachO/MapFile.cpp

43

Do we need to have this ordered? I guess you're trying to not fork the code so passing it into the lambda makes sense, but in general, we could skip the sort for dead stripped symbols.

[Roger]

Rewrite diff to be more declarative.

[Roger]

lld/MachO/MapFile.cpp

43

I guess we don't need to have it ordered. It doesn't look like ld64 orders it. I can take out the ordering if that is better but I don't really know. I've refactored the code a bit but I don't know if that changes anything.

44

@thevinster I decided to encapsulate the "live-ness" of the symbols in their container so the word "Live" now describes the container rather than configure the behavior of the function that dumps symbols. I think the word "Live" is now more appropriate.

@int3 Done.

[Roger]

Small rename.

[mpark]

lld/MachO/MapFile.cpp

44

Maybe just Symbols? There's not much vector about this class aside from an implementation detail. Specifically, you can't use this like a vector at all.

44

Probably want to move these out.

44–45

Seems like you could just make the correct decision here rather than having conditionalInsert do a conditional check.

59

61

177

Seems silly to check the liveness of the container for each element.
It'd be different if you could write C++17 and turn this into an if constexpr,
but otherwise I'd say at least pull this out of the loop such that you only
check this once? Yes the loop would be duplicated but 🤷‍♂️

[Roger]

Rewrite code in a more declarative style.

[Roger]

Addressed mpark's comments.

lld/MachO/MapFile.cpp

44

True.

44

True.

44–45

True. I was trying out pushing conditionals into data structures but this may be taking it too far, yeah.

59

I just got rid of that function.

61

I got rid of that function.

177

I really wanted to make this into an if constexpr. I'll change this to just be two loops.

[Roger]

Update comments.

[Roger]

Reverted from declarative style to a more imperative style.

[Roger]

Update assert

[int3]

lld/MachO/MapFile.cpp

43

outdated comment

177–189

with the if being hoisted out, I'm not sure this writeSymbols function is really factoring out a useful amount of code. How about inlining it?

178–181

I was wondering if this should be !deadSymbols.empty(), but it seems like config->deadStrip is the right one as ld64 will emit the "Dead Stripped Symbols" line as long as -dead_strip is passed. Can we have a test that checks for the case where no symbols get stripped?

lld/test/MachO/dead-strip.s

10

outdated comment

[Roger]

Address comments

[Roger]

Add test with no dead symbols.

[Roger]

lld/MachO/MapFile.cpp

43

The code has changed enough where the original question no longer applies.

177–189

Done.

178–181

I was also thinking about that. I figured it would be better to print the "Dead Stripped Symbols:" header even if there are no dead stripped symbols to explicitly show that there are none. Basing it off the configuration felt like it would make the code would behave with fewest surprises.

[int3]

Nice!

lld/MachO/MapFile.cpp

1

would be good to brew install clang-format :)

lld/test/MachO/dead-strip.s

59

can we call this file something other than map? That way we're not overwriting the map emitted by the earlier command on line 11. That makes debugging the test easier since we can look in the output folder and see the preserved outputs from each command.

70

this could just be NODEADSYMBOLS-EMPTY:, then you wouldn't need the "END OF MAP"

[thevinster]

lld/MachO/MapFile.cpp

181

[Roger]

Address comments

[Roger]

lld/test/MachO/dead-strip.s

59

Done.

70

Done.

[oontvoo]

lld/MachO/MapFile.cpp

45

It seems the deadSymbols is only ever used if config->deadStrip.
Can this function take a flag (eg., includeDead) and not collect or sort dead symbols when the flag is not set?

[int3]

lld/MachO/MapFile.cpp

45

when the flag's not set, the deadSymbols vector will be empty anyway, so sorting will be a no-op.

[oontvoo]

lld/MachO/MapFile.cpp

45

Ah, ok! :)

[Roger]

rebase

lld/MachO/MapFile.cpp

 //===- MapFile.cpp --------------------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the -map option. It shows lists in order and

 #include "llvm/Support/Parallel.h"
 #include "llvm/Support/TimeProfiler.h"
 
 using namespace llvm;
 using namespace llvm::sys;
 using namespace lld;
 using namespace lld::macho;
 
-// 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) {
-            assert(!shouldOmitFromOutput(d->isec));
-            v.push_back(d);
-          }
-
-  parallelSort(v.begin(), v.end(), [](Defined *a, Defined *b) {
-    return a->getVA() != b->getVA() ? a->getVA() < b->getVA()
-                                    : a->getName() < b->getName();
-  });
-  return v;
-}
-
 // Construct a map from symbols to their stringified representations.
 // Demangling symbols (which is what toString() does) is slow, so
 // we do that in batch using parallel-for.
 static DenseMap<Symbol *, std::string>
 getSymbolStrings(ArrayRef<Defined *> syms) {
   std::vector<std::string> str(syms.size());
   parallelForEachN(0, syms.size(), [&](size_t i) {
     raw_string_ostream os(str[i]);
     os << toString(*syms[i]);
   });
 
   DenseMap<Symbol *, std::string> ret;
   for (size_t i = 0, e = syms.size(); i < e; ++i)
     ret[syms[i]] = std::move(str[i]);
   return ret;
 }
 
+namespace {
+
+using ReaderToFileOrdinal = DenseMap<lld::macho::InputFile *, uint32_t>;
+
+template <bool Live> class Symbols {
+public:
+  void push_back(Defined *symbol) {
+    assert(symbol != nullptr);
+    assert(symbol->isLive() == Live);
+    data.push_back(symbol);
+  }
+
+  void sort() {
+    parallelSort(data.begin(), data.end(), [](Defined *a, Defined *b) {
+      return Live && a->getVA() != b->getVA() ? a->getVA() < b->getVA()
+                                              : a->getName() < b->getName();
+    });
+  }
+
+  // Dump table of symbols
+  void print(raw_ostream &os, ReaderToFileOrdinal &readerToFileOrdinal) {
+    DenseMap<Symbol *, std::string> symStr = getSymbolStrings(data);
+    os << "# Address\t    File  Name\n";
+
+    if (Live) {
+      for (Symbol *sym : data) {
+        os << format("0x%08llX\t[%3u] %s\n", sym->getVA(),
+                     readerToFileOrdinal[sym->getFile()], symStr[sym].c_str());
+      }
+    } else {
+      for (Symbol *sym : data) {
+        os << format("<<dead>>\t[%3u] %s\n",
+                     readerToFileOrdinal[sym->getFile()], symStr[sym].c_str());
+      }
+    }
+  };
+
+private:
+  std::vector<Defined *> data;
+};
+
+} // namespace
+
+// Returns only live symbols if `Live` is true. Else, returns only dead-stripped
+// symbols.
+static std::pair<Symbols<true>, Symbols<false>> getSymbols() {
+  Symbols<true> liveSymbols;
+  Symbols<false> deadSymbols;
+  for (InputFile *file : inputFiles)
+    if (isa<ObjFile>(file))
+      for (Symbol *sym : file->symbols)
+        if (auto *d = dyn_cast_or_null<Defined>(sym))
+          if (d->isec && d->getFile() == file) {
+            if (d->isLive()) {
+              assert(!shouldOmitFromOutput(d->isec));
+              liveSymbols.push_back(d);
+            } else {
+              deadSymbols.push_back(d);
+            }
+          }
+
+  liveSymbols.sort();
+  deadSymbols.sort();
+  return std::make_pair(std::move(liveSymbols), std::move(deadSymbols));
+}
+
 void macho::writeMapFile() {
   if (config->mapFile.empty())
     return;
 
   TimeTraceScope timeScope("Write map file");
 
   // Open a map file for writing.
   std::error_code ec;
void macho::writeMapFile() {
   // Dump output architecture.
   os << format("# Arch: %s\n",
                getArchitectureName(config->arch()).str().c_str());
 
   // Dump table of object files.
   os << "# Object files:\n";
   os << format("[%3u] %s\n", 0, (const char *)"linker synthesized");
   uint32_t fileIndex = 1;
-  DenseMap<lld::macho::InputFile *, uint32_t> readerToFileOrdinal;
+  ReaderToFileOrdinal readerToFileOrdinal;
   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();
-  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
+  Symbols<true> liveSymbols;
+  Symbols<false> deadSymbols;
+  std::tie(liveSymbols, deadSymbols) = getSymbols();
+
   os << "# Symbols:\n";
-  os << "# Address\t    File  Name\n";
-  for (Symbol *sym : syms) {
-    os << format("0x%08llX\t[%3u] %s\n", sym->getVA(),
-                 readerToFileOrdinal[sym->getFile()], symStr[sym].c_str());
-  }
+  liveSymbols.print(os, readerToFileOrdinal);
 
-  // TODO: when we implement -dead_strip, we should dump dead stripped symbols
+  if (config->deadStrip) {
+    os << "# Dead Stripped Symbols:\n";
+    deadSymbols.print(os, readerToFileOrdinal);
+  }
 }

lld/test/MachO/dead-strip.s

 # REQUIRES: x86, llvm-64-bits
 
 # RUN: rm -rf %t; split-file %s %t
 
 # RUN: llvm-mc -filetype=obj -triple=x86_64-apple-macos \
 # RUN:     %t/basics.s -o %t/basics.o
 
 ## Check that .private_extern symbols are marked as local in the symbol table
 ## and aren't in the export trie.
 ## Dead-stripped symbols should also not be in a map file output.
 # RUN: %lld -lSystem -dead_strip -map %t/map -u _ref_private_extern_u \
 # RUN:     %t/basics.o -o %t/basics
 # RUN: llvm-objdump --syms --section-headers %t/basics | \
 # RUN:     FileCheck --check-prefix=EXEC --implicit-check-not _unref %s
 # RUN: llvm-objdump --macho --section=__DATA,__ref_section \
 # RUN:     --exports-trie --indirect-symbols %t/basics | \
 # RUN:     FileCheck --check-prefix=EXECDATA --implicit-check-not _unref %s
 # RUN: llvm-otool -l %t/basics | grep -q 'segname __PAGEZERO'
-# RUN: FileCheck --check-prefix=MAP --implicit-check-not _unref %s < %t/map
+# RUN: FileCheck --check-prefix=MAP %s < %t/map
 # EXEC-LABEL: Sections:
 # EXEC-LABEL: Name
 # EXEC-NEXT:  __text
 # EXEC-NEXT:  __got
 # EXEC-NEXT:  __ref_section
 # EXEC-NEXT:  __common
 # EXEC-LABEL: SYMBOL TABLE:
 # EXEC-NEXT:   l {{.*}} _ref_data

 # EXECDATA-NEXT:  _ref_com
 # EXECDATA-LABEL: Contents of (__DATA,__ref_section) section
 # EXECDATA-NEXT:   04 00 00 00 00 00 00 00 05 00 00 00 00 00 00 00
 # EXECDATA-LABEL: Exports trie:
 # EXECDATA-NEXT:   __mh_execute_header
 # EXECDATA-NEXT:   _ref_com
 # EXECDATA-NEXT:   _no_dead_strip_globl
 # MAP: _main
+# MAP-LABEL: Dead Stripped Symbols
+# MAP: <<dead>> [ 1] _unref_com
+# MAP: <<dead>> [ 1] _unref_data
+# MAP: <<dead>> [ 1] _unref_extern
+# MAP: <<dead>> [ 1] _unref_local
+# MAP: <<dead>> [ 1] _unref_private_extern
+# MAP: <<dead>> [ 1] l_unref_data
 
 # RUN: %lld -dylib -dead_strip -u _ref_private_extern_u %t/basics.o -o %t/basics.dylib
 # RUN: llvm-objdump --syms %t/basics.dylib | \
 # RUN:     FileCheck --check-prefix=DYLIB --implicit-check-not _unref %s
 # RUN: %lld -bundle -dead_strip -u _ref_private_extern_u %t/basics.o -o %t/basics.dylib
 # RUN: llvm-objdump --syms %t/basics.dylib | \
 # RUN:     FileCheck --check-prefix=DYLIB --implicit-check-not _unref %s
 # DYLIB-LABEL: SYMBOL TABLE:
 # DYLIB-NEXT:   l {{.*}} _ref_data
 # DYLIB-NEXT:   l {{.*}} _ref_local
 # DYLIB-NEXT:   l {{.*}} _ref_from_no_dead_strip_globl
 # DYLIB-NEXT:   l {{.*}} _no_dead_strip_local
 # DYLIB-NEXT:   l {{.*}} _ref_from_no_dead_strip_local
 # DYLIB-NEXT:   l {{.*}} _ref_private_extern_u
 # DYLIB-NEXT:   l {{.*}} _ref_private_extern
 # DYLIB-NEXT:   g {{.*}} _ref_com
 # DYLIB-NEXT:   g {{.*}} _unref_com
 # DYLIB-NEXT:   g {{.*}} _unref_extern
 # DYLIB-NEXT:   g {{.*}} _no_dead_strip_globl
 
 ## Extern symbols aren't stripped from executables with -export_dynamic
 # RUN: %lld -lSystem -dead_strip -export_dynamic -u _ref_private_extern_u \
 # RUN:     %t/basics.o -o %t/basics-export-dyn
 # RUN: llvm-objdump --syms --section-headers %t/basics-export-dyn | \