[lld/mac] Implement -dead_strip

[thakis]

Summary

Also adds support for live_support sections, no_dead_strip sections,
.no_dead_strip symbols.

Chromium Framework 345MB unstripped -> 250MB stripped
(vs 290MB unstripped -> 236M stripped with ld64).

Doing dead stripping is a bit faster than not, because so much less
data needs to be processed:

% ministat lld_*
x lld_nostrip.txt
+ lld_strip.txt
    N           Min           Max        Median           Avg        Stddev
x  10      3.929414       4.07692     4.0269079     4.0089678   0.044214794
+  10     3.8129408     3.9025559     3.8670411     3.8642573   0.024779651
Difference at 95.0% confidence
        -0.144711 +/- 0.0336749
        -3.60967% +/- 0.839989%
        (Student's t, pooled s = 0.0358398)

This interacts with many parts of the linker. I tried to add test coverage
for all added isLive() checks, so that some test will fail if any of them
is removed. I checked that the test expectations for the most part match
ld64's behavior (except for live-support-iterations.s, see the comment
in the test). Interacts with:

• debug info
• export tries
• import opcodes
• flags like -exported_symbol(s_list)
• -U / dynamic_lookup
• mod_init_funcs, mod_term_funcs
• weak symbol handling
• unwind info
• stubs
• map files
• -sectcreate
• undefined, dylib, common, defined (both absolute and normal) symbols

It's possible it interacts with more features I didn't think of,
of course.

I also did some manual testing:

• check-llvm check-clang check-lld work with lld with this patch as host linker and -dead_strip enabled
• Chromium still starts
• Chromium's base_unittests still pass, including unwind tests

Implemenation-wise, this is InputSection-based, so it'll work for
object files with .subsections_via_symbols (which includes all
object files generated by clang). I first based this on the COFF
implementation, but later realized that things are more similar to ELF.
I think it'd be good to refactor MarkLive.cpp to look more like the ELF
part at some point, but I'd like to get a working state checked in first.

Mechanical parts:

• Rename canOmitFromOutput to wasCoalesced (no behavior change) since it really is for weak coalesced symbols
• Add noDeadStrip to Defined, corresponding to N_NO_DEAD_STRIP (.no_dead_strip in asm)

Fixes PR49276.

[tschuett]

Thanks! Iget:

= note: lld: error: unknown argument '-dead_strip'

[thakis]

minor tweak to a comment

[thakis]

In D103324#2787192, @tschuett wrote:

Thanks! Iget:

= note: lld: error: unknown argument '-dead_strip'

…with this patch applied? If so, are you invoking lld trough the ld64.lld symlink to get the MachO driver?

[tschuett]

Sorry. Before this patch. I am trying to link Rust.

[thakis]

In D103324#2787222, @tschuett wrote:

Sorry. Before this patch. I am trying to link Rust.

Ah, I see . I'd recommend not passing -Wl,-fatal_warnings, then that's only a warning :) (But that particular diag will go away once this patch is in.)

[tschuett]

Sorry for bothering with this with ld64.lld:

= note: ld64.lld: error: unknown argument '-m64'
        ld64.lld: error: unknown argument '-Wl,-dead_strip'
        ld64.lld: error: unknown argument '-nodefaultlibs'
        ld64.lld: error: must specify -platform_version

[thakis]

In D103324#2787238, @tschuett wrote:

Sorry for bothering with this with ld64.lld:

= note: ld64.lld: error: unknown argument '-m64'
        ld64.lld: error: unknown argument '-Wl,-dead_strip'
        ld64.lld: error: unknown argument '-nodefaultlibs'
        ld64.lld: error: must specify -platform_version

Oh, if you call it through clang (which is the normal way), just -fuse-ld=lld does the right thing. This is really off topic for this review try though 😃

[thakis]

make clang-format happy

not sure what clang-tidy wants from me though, that header guard looks fine. would be nice if that check had more details.

[tschuett]

In D103324#2787281, @thakis wrote:

In D103324#2787238, @tschuett wrote:

Sorry for bothering with this with ld64.lld:

= note: ld64.lld: error: unknown argument '-m64'
        ld64.lld: error: unknown argument '-Wl,-dead_strip'
        ld64.lld: error: unknown argument '-nodefaultlibs'
        ld64.lld: error: must specify -platform_version

Oh, if you call it through clang (which is the normal way), just -fuse-ld=lld does the right thing. This is really off topic for this review try though 😃

The last off topic comment. The rust compiler invokes the linker: https://doc.rust-lang.org/rustc/codegen-options/index.html#linker

[tschuett]

In D103324#2787404, @thakis wrote:

make clang-format happy

not sure what clang-tidy wants from me though, that header guard looks fine. would be nice if that check had more details.

Maybe clang-tidy is in general unhappy with the MachO style, but it only complains about new files.

[thakis]

tiny cosmetic tweaks

[thakis]

more tiny cosmetic tweaks and some more clang-format appeasing

[int3]

Nice work :D

lld/MachO/Driver.cpp

930

can we put this together with the other config init lines around line 969?

edit: ah, I guess it's because Symbol's ctor uses it... a comment would be good. Although -- what do you think about always marking Symbols/InputSections as not-live and then have isLive() check for !config->deadStrip? I guess there'll be a bit more runtime overhead but not sure it'd be significant...

hm I see the other LLD ports have also implemented things this way :/

lld/MachO/InputSection.h

51

64

it seems a bit counterintuitive to me that something can be live even though it has been coalesced away :) having live default to false (as mentioned in my comment in Driver.cpp) would avoid this issue too

lld/MachO/MarkLive.cpp

28

This is a pretty large function, can we break it up? Maybe have the seed-marking vs transitive-closure-marking as separate functions

29

when should we use ScopedTimer over TimeTraceScope? also, I don't think we call Timer::print() anywhere...

108–109

124

I'd personally prefer target->wordSize == 8 ? sizeof(CompactUnwindEntry<uint64_t>) : sizeof(CompactUnwindEntry<uint32_t>). More verbose but also more explicit

lld/MachO/Symbols.cpp

43

seems clearer this way imo

lld/MachO/Symbols.h

113

nit for mach-o terminology consistency

lld/test/MachO/dead-strip.s

12

28–38

nit: the first {{.*}} on each line is unnecessary

43

128–129

is this line meant to check that no bindings are present in the bind table? I don't think it does the job... I think you want something like

STRIPDYLIB: Bind table:
STRIDYLIB-EMPTY:
STRIPDYLIB-NEXT: Lazy bind table:

214

243–245

nit: please align :D

562

lld/test/MachO/mh-header-link.s

12

why is this necessary?

[thakis]

address comments

lld/MachO/Driver.cpp

930

Added a comment.

Right, it's for consistency with the other LLD ports. I had the explicit check in isLive first but I moved to this for consistency with the other LLDs and for some other reason I no longer remember. Maybe used in Symbol needed an accessor for reading then? Not sure that was it. It felt marginally nicer this way :)

lld/MachO/InputSection.h

64

If dead stripping is on, all coalesced weak InputSections should also be marked !live.

If dead stripping is not on, then yes, this can happen. It's a bit strange, but it matches the other ports.

lld/MachO/MarkLive.cpp

28

Yes, that's what I was getting at with

"""
I first based this on the COFF
implementation, but later realized that things are more similar to ELF.
I think it'd be good to refactor MarkLive.cpp to look more like the ELF
part at some point, but I'd like to get a working state checked in first.
"""

The ELF port has a class with member functions and stuff, and I agree that the root collecting code should be its own function. If it's ok I'd like to iterate on this in-tree though.

(I also have a local branch that implements -why_live … actually let me upload that, D103517 … but implementing it the same way ld64 did is too expensive perf wise, so I don't know yet if I need to templatize this on the state bit or made dead_strip independent of why_live or what. And finally, it feels like several pieces of code walk all files just to iterate all local symbols, so maybe I'd to pull the localSymbols computation out of SyntheticSections.cpp and then use that in the several places that use it. And speaking of local symbols, the order file processing currently walks all symbols, exported and local, and checks each against the order file, even though if the order file is short and only contains public symbols it should be way faster to walk the order file and look each symbol up in the symbol table instead, then it's small-constant-times-amortized-linear-of-large instead of large-constant-times-amortized-linear-of-small.)

Sorry about the wall of text! Summary: I agree I should do this, but I'd like to do it after getting the first draft committed :)

29

Good catch. Apparently the COFF port uses ScopedTimer (for its fancy /time feature), while ELF and MachO use TimeTraceScope (for their fancy trace export). I think I should change TimeTraceScope to also be able to print time reports, then switch COFF to that so that it grows a fancy trace export, and then give the ELF and MachO ports flags for a time report on the console. (For MachO, I guess that'd go behind -print_statistics which already exists.)

For now, changed this to TimeTraceScope.

124

Also requires putting CompactUnwindEntry in the header. But sure, done.

lld/test/MachO/dead-strip.s

128–129

IIRC the --implicit-check-not _unref does most of the work and this here just checks that I remembered to pass --bind

lld/test/MachO/mh-header-link.s

12

Good question. I think it was test coverage for making sure createSyntheticSymbols() works with dead stripping. I think in the end it just worked without any changes, but I figured it's still nice to have the coverage.

[int3]

lgtm

lld/MachO/MarkLive.cpp

28

no need for llvm::

[thakis]

Thanks! :)

lld/MachO/MarkLive.cpp

28

../../lld/MachO/MarkLive.cpp:27:3: error: unknown type name 'TimeTraceScope'; did you mean 'llvm::TimeTraceScope'?

(Added a using namespace llvm; for it)

[DavidSpickett]

@thakis dead-strip.s has been failing on our 32 bit armv8 bot: https://lab.llvm.org/buildbot/#/builders/178/builds/42
(I think we missed when this started due to some bot config changes we were doing)

I've disabled it for 32 bit builds in: https://reviews.llvm.org/rG6942076096e6dcfb0893a351a9a586490beec572

Seems like some of the symbol names change order when built for 32 bit. At least that's my guess, doesn't seem like an Arm specific thing unless it's distro related somehow. Happens with GCC or clang built lld.

Expected:

# UNWIND-NEXT:   g F __TEXT,__text __mh_execute_header
# UNWIND-NEXT:   *UND* ___cxa_allocate_exception
# UNWIND-NEXT:   *UND* ___cxa_end_catch
# UNWIND-NEXT:   *UND* __ZTIi
# UNWIND-NEXT:   *UND* ___cxa_throw
# UNWIND-NEXT:   *UND* ___gxx_personality_v0
# UNWIND-NEXT:   *UND* ___cxa_begin_catch
# UNWIND-NEXT:   *UND* dyld_stub_binder

Got:

 8: 0000000100000000 g F __TEXT,__text __mh_execute_header
 9: 0000000000000000 *UND* __ZTIi
10: 0000000000000000 *UND* ___gxx_personality_v0
11: 0000000000000000 *UND* ___cxa_throw
12: 0000000000000000 *UND* ___cxa_end_catch
13: 0000000000000000 *UND* ___cxa_allocate_exception
14: 0000000000000000 *UND* ___cxa_begin_catch
15: 0000000000000000 *UND* dyld_stub_binder

Any ideas?

lld/MachO/CMakeLists.txt

add_lld_library(lldMachO2
   Driver.cpp
   DriverUtils.cpp
   Dwarf.cpp
   ExportTrie.cpp
   InputFiles.cpp
   InputSection.cpp
   LTO.cpp
   MapFile.cpp
+  MarkLive.cpp
   ObjC.cpp
   OutputSection.cpp
   OutputSegment.cpp
   Relocations.cpp
   SymbolTable.cpp
   Symbols.cpp
   SyntheticSections.cpp
   Target.cpp

lld/MachO/ConcatOutputSection.cpp

for (Reloc &r : reverse(relocs)) {
       thunkInfo.isec->name = isec->name;
       thunkInfo.isec->segname = isec->segname;
       thunkInfo.isec->parent = this;
       StringRef thunkName = saver.save(funcSym->getName() + ".thunk." +
                                        std::to_string(thunkInfo.sequence++));
       r.referent = thunkInfo.sym = symtab->addDefined(
           thunkName, /*file=*/nullptr, thunkInfo.isec, /*value=*/0,
           /*size=*/thunkSize, /*isWeakDef=*/false, /*isPrivateExtern=*/true,
-          /*isThumb=*/false, /*isReferencedDynamically=*/false);
+          /*isThumb=*/false, /*isReferencedDynamically=*/false,
+          /*noDeadStrip=*/false);
       target->populateThunk(thunkInfo.isec, funcSym);
       finalizeOne(thunkInfo.isec);
       thunks.push_back(thunkInfo.isec);
       ++thunkCount;
     }
   }
   size = isecAddr - addr;
   fileSize = isecFileOff - fileOff;

lld/MachO/Config.h

struct Configuration {
   uint32_t timeTraceGranularity = 500;
   std::string progName;
   llvm::StringRef installName;
   llvm::StringRef mapFile;
   llvm::StringRef outputFile;
   llvm::StringRef ltoObjPath;
   llvm::StringRef thinLTOJobs;
   bool demangle = false;
+  bool deadStrip = false;
   PlatformInfo platformInfo;
   NamespaceKind namespaceKind = NamespaceKind::twolevel;
   UndefinedSymbolTreatment undefinedSymbolTreatment =
       UndefinedSymbolTreatment::error;
   llvm::MachO::HeaderFileType outputType;
   std::vector<llvm::StringRef> systemLibraryRoots;
   std::vector<llvm::StringRef> librarySearchPaths;
   std::vector<llvm::StringRef> frameworkSearchPaths;

lld/MachO/Driver.cpp

 //===- Driver.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
 //
 //===----------------------------------------------------------------------===//
 
 #include "Driver.h"
 #include "Config.h"
 #include "InputFiles.h"
 #include "LTO.h"
+#include "MarkLive.h"
 #include "ObjC.h"
 #include "OutputSection.h"
 #include "OutputSegment.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "SyntheticSections.h"
 #include "Target.h"
 #include "Writer.h"
for (Symbol *sym : symtab->getSymbols()) {
     isec->align = common->align;
     // Casting to size_t will truncate large values on 32-bit architectures,
     // but it's not really worth supporting the linking of 64-bit programs on
     // 32-bit archs.
     isec->data = {nullptr, static_cast<size_t>(common->size)};
     isec->flags = S_ZEROFILL;
     inputSections.push_back(isec);
 
+    // FIXME: CommonSymbol should store isReferencedDynamically, noDeadStrip
+    // and pass them on here.
     replaceSymbol<Defined>(sym, sym->getName(), isec->file, isec, /*value=*/0,
                            /*size=*/0,
                            /*isWeakDef=*/false,
                            /*isExternal=*/true, common->privateExtern,
                            /*isThumb=*/false,
-                           /*isReferencedDynamically=*/false);
+                           /*isReferencedDynamically=*/false,
+                           /*noDeadStrip=*/false);
   }
 }
 
 static void initializeSectionRenameMap() {
   if (config->dataConst) {
     SmallVector<StringRef> v{section_names::got,
                              section_names::authGot,
                              section_names::authPtr,
bool macho::link(ArrayRef<const char *> argsArr, bool canExitEarly,
   }
 
   config = make<Configuration>();
   symtab = make<SymbolTable>();
   target = createTargetInfo(args);
   depTracker =
       make<DependencyTracker>(args.getLastArgValue(OPT_dependency_info));
 
+  config->deadStrip = args.hasArg(OPT_dead_strip);
+
   config->systemLibraryRoots = getSystemLibraryRoots(args);
   if (const char *path = getReproduceOption(args)) {
     // Note that --reproduce is a debug option so you can ignore it
     // if you are trying to understand the whole picture of the code.
     Expected<std::unique_ptr<TarWriter>> errOrWriter =
         TarWriter::create(path, path::stem(path));
     if (errOrWriter) {
       tar = std::move(*errOrWriter);
for (const Arg *arg : args.filtered(OPT_sectcreate)) {
       // Gather all InputSections into one vector.
       for (const InputFile *file : inputFiles) {
         for (const SubsectionMap &map : file->subsections)
           for (const SubsectionEntry &subsectionEntry : map)
             inputSections.push_back(subsectionEntry.isec);
       }
     }
 
+    if (config->deadStrip)
+      markLive();
+
     // Write to an output file.
     if (target->wordSize == 8)
       writeResult<LP64>();
     else
       writeResult<ILP32>();
 
     depTracker->write(getLLDVersion(), inputFiles, config->outputFile);
   }

lld/MachO/InputFiles.cpp

if (sym.n_type & (N_EXT | N_PEXT)) {
     // definition will continue to take priority if more private extern
     // definitions are encountered. With lld's semantics there's no observable
     // difference between a symbol that's isWeakDefCanBeHidden or one that's
     // privateExtern -- neither makes it into the dynamic symbol table. So just
     // promote isWeakDefCanBeHidden to isPrivateExtern here.
     if (isWeakDefCanBeHidden)
       isPrivateExtern = true;
 
-    return symtab->addDefined(name, isec->file, isec, value, size,
-                              sym.n_desc & N_WEAK_DEF, isPrivateExtern,
-                              sym.n_desc & N_ARM_THUMB_DEF,
-                              sym.n_desc & REFERENCED_DYNAMICALLY);
+    return symtab->addDefined(
+        name, isec->file, isec, value, size, sym.n_desc & N_WEAK_DEF,
+        isPrivateExtern, sym.n_desc & N_ARM_THUMB_DEF,
+        sym.n_desc & REFERENCED_DYNAMICALLY, sym.n_desc & N_NO_DEAD_STRIP);
   }
 
   assert(!isWeakDefCanBeHidden &&
          "weak_def_can_be_hidden on already-hidden symbol?");
   return make<Defined>(
       name, isec->file, isec, value, size, sym.n_desc & N_WEAK_DEF,
       /*isExternal=*/false, /*isPrivateExtern=*/false,
-      sym.n_desc & N_ARM_THUMB_DEF, sym.n_desc & REFERENCED_DYNAMICALLY);
+      sym.n_desc & N_ARM_THUMB_DEF, sym.n_desc & REFERENCED_DYNAMICALLY,
+      sym.n_desc & N_NO_DEAD_STRIP);
 }
 
 // Absolute symbols are defined symbols that do not have an associated
 // InputSection. They cannot be weak.
 template <class NList>
 static macho::Symbol *createAbsolute(const NList &sym, InputFile *file,
                                      StringRef name) {
   if (sym.n_type & (N_EXT | N_PEXT)) {
     assert((sym.n_type & N_EXT) && "invalid input");
     return symtab->addDefined(name, file, nullptr, sym.n_value, /*size=*/0,
                               /*isWeakDef=*/false, sym.n_type & N_PEXT,
                               sym.n_desc & N_ARM_THUMB_DEF,
-                              /*isReferencedDynamically=*/false);
+                              /*isReferencedDynamically=*/false,
+                              sym.n_desc & N_NO_DEAD_STRIP);
   }
   return make<Defined>(name, file, nullptr, sym.n_value, /*size=*/0,
                        /*isWeakDef=*/false,
                        /*isExternal=*/false, /*isPrivateExtern=*/false,
                        sym.n_desc & N_ARM_THUMB_DEF,
-                       /*isReferencedDynamically=*/false);
+                       /*isReferencedDynamically=*/false,
+                       sym.n_desc & N_NO_DEAD_STRIP);
 }
 
 template <class NList>
 macho::Symbol *ObjFile::parseNonSectionSymbol(const NList &sym,
                                               StringRef name) {
   uint8_t type = sym.n_type & N_TYPE;
   switch (type) {
   case N_UNDF:
for (size_t j = 0; j < symbolIndices.size(); ++j) {
         symbols[symIndex] =
             createDefined(sym, name, isec, symbolOffset, symbolSize);
         continue;
       }
 
       auto *nextIsec = make<InputSection>(*isec);
       nextIsec->data = isec->data.slice(symbolOffset);
       nextIsec->numRefs = 0;
-      nextIsec->canOmitFromOutput = false;
+      nextIsec->wasCoalesced = false;
       isec->data = isec->data.slice(0, symbolOffset);
 
       // By construction, the symbol will be at offset zero in the new
       // subsection.
       symbols[symIndex] =
           createDefined(sym, name, nextIsec, /*value=*/0, symbolSize);
       // TODO: ld64 appears to preserve the original alignment as well as each
       // subsection's offset from the last aligned address. We should consider
OpaqueFile::OpaqueFile(MemoryBufferRef mb, StringRef segName,
                        StringRef sectName)
     : InputFile(OpaqueKind, mb) {
   InputSection *isec = make<InputSection>();
   isec->file = this;
   isec->name = sectName.take_front(16);
   isec->segname = segName.take_front(16);
   const auto *buf = reinterpret_cast<const uint8_t *>(mb.getBufferStart());
   isec->data = {buf, mb.getBufferSize()};
+  isec->live = true;
   subsections.push_back({{0, isec}});
 }
 
 ObjFile::ObjFile(MemoryBufferRef mb, uint32_t modTime, StringRef archiveName)
     : InputFile(ObjKind, mb), modTime(modTime) {
   this->archiveName = std::string(archiveName);
   if (target->wordSize == 8)
     parse<LP64>();
case GlobalValue::ProtectedVisibility:
     break;
   case GlobalValue::DefaultVisibility:
     break;
   }
 
   return symtab->addDefined(name, &file, /*isec=*/nullptr, /*value=*/0,
                             /*size=*/0, objSym.isWeak(), isPrivateExtern,
                             /*isThumb=*/false,
-                            /*isReferencedDynamically=*/false);
+                            /*isReferencedDynamically=*/false,
+                            /*noDeadStrip=*/false);
 }
 
 BitcodeFile::BitcodeFile(MemoryBufferRef mbref)
     : InputFile(BitcodeKind, mbref) {
   obj = check(lto::InputFile::create(mbref));
 
   // Convert LTO Symbols to LLD Symbols in order to perform resolution. The
   // "winning" symbol will then be marked as Prevailing at LTO compilation
   // time.
   for (const lto::InputFile::Symbol &objSym : obj->symbols())
     symbols.push_back(createBitcodeSymbol(objSym, *this));
 }
 
 template void ObjFile::parse<LP64>();

lld/MachO/InputSection.h

 //===- InputSection.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_INPUT_SECTION_H
 #define LLD_MACHO_INPUT_SECTION_H
 
+#include "Config.h"
 #include "Relocations.h"
 
 #include "lld/Common/LLVM.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/BinaryFormat/MachO.h"
 
 namespace lld {
 namespace macho {
public:
   uint32_t align = 1;
   uint32_t flags = 0;
   uint32_t callSiteCount = 0;
   bool isFinal = false; // is address assigned?
 
   // How many symbols refer to this InputSection.
   uint32_t numRefs = 0;
 
-  // True if this InputSection could not be written to the output file.
   // With subsections_via_symbols, most symbol have its own InputSection,
   // and for weak symbols (e.g. from inline functions), only the
   // InputSection from one translation unit will make it to the output,
   // while all copies in other translation units are coalesced into the
   // first and not copied to the output.
-  bool canOmitFromOutput = false;
+  bool wasCoalesced = false;
 
+  bool isCoalescedWeak() const {
+    return wasCoalesced && numRefs == 0;
+  }
   bool shouldOmitFromOutput() const {
-    return canOmitFromOutput && numRefs == 0;
+    return !live || isCoalescedWeak();
   }
 
+  bool live = !config->deadStrip;
+
   ArrayRef<uint8_t> data;
   std::vector<Reloc> relocs;
 };
 
 inline uint8_t sectionType(uint32_t flags) {
   return flags & llvm::MachO::SECTION_TYPE;
 }
 

lld/MachO/MapFile.cpp

 }
 
 // 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 (sym == nullptr)
-          continue;
-        if (auto *d = dyn_cast<Defined>(sym))
-          if (d->isec && d->getFile() == file) {
-            assert(!d->isec->shouldOmitFromOutput() &&
+        if (auto *d = dyn_cast_or_null<Defined>(sym))
+          if (d->isLive() && d->isec && d->getFile() == file) {
+            assert(!d->isec->isCoalescedWeak() &&
                    "file->symbols should store resolved symbols");
             v.push_back(d);
           }
       }
   return v;
 }
 
 // Construct a map from symbols to their stringified representations.

lld/MachO/MarkLive.h

+//===- MarkLive.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_MARKLIVE_H
+#define LLD_MACHO_MARKLIVE_H
+
+namespace lld {
+namespace macho {
+
+class InputSection;
+void markLive();
+
+} // namespace macho
+} // namespace lld
+
+#endif // LLD_MACHO_MARKLIVE_H

lld/MachO/MarkLive.cpp

+//===- MarkLive.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
+//
+//===----------------------------------------------------------------------===//
+
+#include "MarkLive.h"
+#include "Config.h"
+#include "OutputSegment.h"
+#include "SymbolTable.h"
+#include "Symbols.h"
+#include "lld/Common/Timer.h"
+#include "mach-o/compact_unwind_encoding.h"
+#include "llvm/ADT/STLExtras.h"
+#include <vector>
+
+namespace lld {
+namespace macho {
+
+using namespace llvm::MachO;
+
+static Timer gctimer("GC", Timer::root());
+
+// Set live bit on for each reachable chunk. Unmarked (unreachable)
+// InputSections will be ignored by Writer, so they will be excluded
+// from the final output.
+void markLive() {
+  ScopedTimer t(gctimer);
+
+  // We build up a worklist of sections which have been marked as live. We only
+  // push into the worklist when we discover an unmarked section, and we mark
+  // as we push, so sections never appear twice in the list.
+  SmallVector<InputSection *, 256> worklist;
+
+  auto enqueue = [&](InputSection *s) {
+    if (s->live)
+      return;
+    s->live = true;
+    worklist.push_back(s);
+  };
+
+  auto addSym = [&](Symbol *s) {
+    s->used = true;
+    if (auto *d = dyn_cast<Defined>(s))
+      if (d->isec)
+        enqueue(d->isec);
+  };
+
+  // Add GC roots.
+  if (config->entry)
+    addSym(config->entry);
+  for (Symbol *sym : symtab->getSymbols()) {
+    if (auto *defined = dyn_cast<Defined>(sym)) {
+      // -exported_symbol(s_list)
+      if (!config->exportedSymbols.empty() &&
+          config->exportedSymbols.match(defined->getName())) {
+        // FIXME: Instead of doing this here, maybe the Driver code doing
+        // the matching should add them to explicitUndefineds? Then the
+        // explicitUndefineds code below would handle this automatically.
+        assert(!defined->privateExtern && "should have been rejected by driver");
+        addSym(defined);
+        continue;
+      }
+
+      // public symbols explicitly marked .no_dead_strip
+      if (defined->referencedDynamically || defined->noDeadStrip) {
+        addSym(defined);
+        continue;
+      }
+
+      // FIXME: When we implement these flags, make symbols from them GC roots:
+      // * -reexported_symbol(s_list)
+      // * -alias(-list)
+      // * -init
+
+      // In dylibs and bundles, all external functions are GC roots.
+      // FIXME: -export_dynamic should enable this for executables too.
+      if (config->outputType != MH_EXECUTE && !defined->privateExtern) {
+        addSym(defined);
+        continue;
+      }
+    }
+  }
+  // -u symbols
+  for (Symbol *sym : config->explicitUndefineds) {
+    if (auto *defined = dyn_cast<Defined>(sym))
+        addSym(defined);
+  }
+  // local symbols explicitly marked .no_dead_strip
+  for (const InputFile *file : inputFiles)
+    if (auto *objFile = dyn_cast<ObjFile>(file))
+      for (Symbol *sym : objFile->symbols)
+        if (auto *defined = dyn_cast_or_null<Defined>(sym))
+          if (!defined->isExternal() && defined->noDeadStrip)
+            addSym(defined);
+  if (auto *stubBinder = dyn_cast_or_null<DylibSymbol>(symtab->find("dyld_stub_binder")))
+    addSym(stubBinder);
+  for (InputSection *isec : inputSections) {
+    if (isec->live)
+      continue;
+
+    // Sections marked no_dead_strip
+    if (isec->flags & S_ATTR_NO_DEAD_STRIP) {
+      enqueue(isec);
+      continue;
+    }
+
+    // mod_init_funcs, mod_term_funcs sections
+    if ((isec->flags & SECTION_TYPE) == S_MOD_INIT_FUNC_POINTERS ||
+        (isec->flags & SECTION_TYPE) == S_MOD_TERM_FUNC_POINTERS) {
+      enqueue(isec);
+      continue;
+    }
+
+    // Dead strip runs before UnwindInfoSection handling so we need to keep
+    // __LD,__compact_unwind alive here.
+    // But that section contains absolute references to __TEXT,__text and
+    // keeps most code alive due to that. So we can't just enqueue() the
+    // section: We must skip the relocations for the functionAddress
+    // in each CompactUnwindEntry.
+    // See also scanEhFrameSection() in lld/ELF/MarkLive.cpp.
+    if (isec->segname == segment_names::ld &&
+        isec->name == section_names::compactUnwind) {
+      isec->live = true;
+      const int compactUnwindEntrySize = 3 * target->wordSize +
+                                         sizeof(compact_unwind_encoding_t) +
+                                         sizeof(uint32_t);
+      for (const Reloc &r : isec->relocs) {
+        // This is the relocation for the address of the function itself.
+        // Ignore it, else these would keep everything alive.
+        if (r.offset % compactUnwindEntrySize == 0)
+          continue;
+
+        if (auto *s = r.referent.dyn_cast<Symbol *>())
+          addSym(s);
+        else {
+          auto *referentIsec = r.referent.get<InputSection *>();
+          assert(!referentIsec->isCoalescedWeak());
+          enqueue(r.referent.get<InputSection *>());
+        }
+      }
+      continue;
+    }
+  }
+
+  do {
+    // Mark things reachable from GC roots as live.
+    while (!worklist.empty()) {
+      InputSection *s = worklist.pop_back_val();
+      assert(s->live && "We mark as live when pushing onto the worklist!");
+
+      // Mark all symbols listed in the relocation table for this section.
+      for (const Reloc &r : s->relocs) {
+        if (auto *s = r.referent.dyn_cast<Symbol *>()) {
+          addSym(s);
+        } else {
+          auto *referentIsec = r.referent.get<InputSection *>();
+          assert(!referentIsec->isCoalescedWeak());
+          enqueue(referentIsec);
+        }
+      }
+    }
+
+    // S_ATTR_LIVE_SUPPORT sections are live if they point _to_ a live section.
+    // Process them in a second pass.
+    for (InputSection *isec : inputSections) {
+      // FIXME: Check if copying all S_ATTR_LIVE_SUPPORT sections into a
+      // separate vector and only walking that here is faster.
+      if (!(isec->flags & S_ATTR_LIVE_SUPPORT) || isec->live)
+        continue;
+
+      for (const Reloc &r : isec->relocs) {
+        bool referentLive;
+        if (auto *s = r.referent.dyn_cast<Symbol *>())
+          referentLive = s->isLive();
+        else
+          referentLive = r.referent.get<InputSection *>()->live;
+        if (referentLive)
+          enqueue(isec);
+      }
+    }
+
+    // S_ATTR_LIVE_SUPPORT could have marked additional sections live,
+    // which in turn could mark additional S_ATTR_LIVE_SUPPORT sections live.
+    // Iterate. In practice, the second iteration won't mark additional
+    // S_ATTR_LIVE_SUPPORT sections live.
+  } while (!worklist.empty());
+}
+
+} // namespace macho
+} // namespace lld

lld/MachO/Options.td

def dtrace : Separate<["-"], "dtrace">,
     HelpText<"Enable DTrace static probes according to declarations in <script>">,
     Flags<[HelpHidden]>,
     Group<grp_content>;
 
 def grp_opts : OptionGroup<"opts">, HelpText<"OPTIMIZATIONS">;
 
 def dead_strip : Flag<["-"], "dead_strip">,
     HelpText<"Remove unreachable functions and data">,
-    Flags<[HelpHidden]>,
     Group<grp_opts>;
 def order_file : Separate<["-"], "order_file">,
     MetaVarName<"<file>">,
     HelpText<"Layout functions and data according to specification in <file>">,
     Group<grp_opts>;
 def no_order_inits : Flag<["-"], "no_order_inits">,
     HelpText<"Disable default reordering of initializer and terminator functions">,
     Flags<[HelpHidden]>,

lld/MachO/SymbolTable.h

  * new`. Therefore, there is no need to update any relocations that hold
  * pointers the "old" Symbol -- they will automatically point to the new one.
  */
 class SymbolTable {
 public:
   Defined *addDefined(StringRef name, InputFile *, InputSection *,
                       uint64_t value, uint64_t size, bool isWeakDef,
                       bool isPrivateExtern, bool isThumb,
-                      bool isReferencedDynamically);
+                      bool isReferencedDynamically, bool noDeadStrip);
 
   Symbol *addUndefined(StringRef name, InputFile *, bool isWeakRef);
 
   Symbol *addCommon(StringRef name, InputFile *, uint64_t size, uint32_t align,
                     bool isPrivateExtern);
 
   Symbol *addDylib(StringRef name, DylibFile *file, bool isWeakDef, bool isTlv);
   Symbol *addDynamicLookup(StringRef name);

lld/MachO/SymbolTable.cpp

std::pair<Symbol *, bool> SymbolTable::insert(StringRef name,
   sym->isUsedInRegularObj |= !file || isa<ObjFile>(file);
   return {sym, p.second};
 }
 
 Defined *SymbolTable::addDefined(StringRef name, InputFile *file,
                                  InputSection *isec, uint64_t value,
                                  uint64_t size, bool isWeakDef,
                                  bool isPrivateExtern, bool isThumb,
-                                 bool isReferencedDynamically) {
+                                 bool isReferencedDynamically,
+                                 bool noDeadStrip) {
   Symbol *s;
   bool wasInserted;
   bool overridesWeakDef = false;
   std::tie(s, wasInserted) = insert(name, file);
 
   assert(!isWeakDef || (isa<BitcodeFile>(file) && !isec) ||
          (isa<ObjFile>(file) && file == isec->file));
 
   if (!wasInserted) {
     if (auto *defined = dyn_cast<Defined>(s)) {
       if (isWeakDef) {
         if (defined->isWeakDef()) {
           // Both old and new symbol weak (e.g. inline function in two TUs):
           // If one of them isn't private extern, the merged symbol isn't.
           defined->privateExtern &= isPrivateExtern;
           defined->referencedDynamically |= isReferencedDynamically;
+          defined->noDeadStrip |= noDeadStrip;
 
           // FIXME: Handle this for bitcode files.
           // FIXME: We currently only do this if both symbols are weak.
           //        We could do this if either is weak (but getting the
           //        case where !isWeakDef && defined->isWeakDef() right
           //        requires some care and testing).
           if (isec)
-            isec->canOmitFromOutput = true;
+            isec->wasCoalesced = true;
         }
 
         return defined;
       }
       if (!defined->isWeakDef())
         error("duplicate symbol: " + name + "\n>>> defined in " +
               toString(defined->getFile()) + "\n>>> defined in " +
               toString(file));
     } else if (auto *dysym = dyn_cast<DylibSymbol>(s)) {
       overridesWeakDef = !isWeakDef && dysym->isWeakDef();
     }
     // Defined symbols take priority over other types of symbols, so in case
     // of a name conflict, we fall through to the replaceSymbol() call below.
   }
 
   Defined *defined = replaceSymbol<Defined>(
       s, name, file, isec, value, size, isWeakDef, /*isExternal=*/true,
-      isPrivateExtern, isThumb, isReferencedDynamically);
+      isPrivateExtern, isThumb, isReferencedDynamically, noDeadStrip);
   defined->overridesWeakDef = overridesWeakDef;
   return defined;
 }
 
 Symbol *SymbolTable::addUndefined(StringRef name, InputFile *file,
                                   bool isWeakRef) {
   Symbol *s;
   bool wasInserted;

 }
 
 Defined *SymbolTable::addSynthetic(StringRef name, InputSection *isec,
                                    uint64_t value, bool isPrivateExtern,
                                    bool includeInSymtab,
                                    bool referencedDynamically) {
   Defined *s = addDefined(name, nullptr, isec, value, /*size=*/0,
                           /*isWeakDef=*/false, isPrivateExtern,
-                          /*isThumb=*/false, referencedDynamically);
+                          /*isThumb=*/false, referencedDynamically,
+                          /*noDeadStrip=*/false);
   s->includeInSymtab = includeInSymtab;
   return s;
 }
 
 void lld::macho::treatUndefinedSymbol(const Undefined &sym, StringRef source) {
   auto message = [source, &sym]() {
     std::string message = "undefined symbol: " + toString(sym);
     if (!source.empty())

lld/MachO/Symbols.h

public:
   Kind kind() const { return symbolKind; }
 
   StringRef getName() const {
     if (nameSize == (uint32_t)-1)
       nameSize = strlen(nameData);
     return {nameData, nameSize};
   }
 
+  bool isLive() const;
+
   virtual uint64_t getVA() const { return 0; }
 
   virtual uint64_t getFileOffset() const {
     llvm_unreachable("attempt to get an offset from a non-defined symbol");
   }
 
   virtual bool isWeakDef() const { llvm_unreachable("cannot be weak def"); }
 
public:
 
   uint32_t symtabIndex = UINT32_MAX;
 
   InputFile *getFile() const { return file; }
 
 protected:
   Symbol(Kind k, StringRefZ name, InputFile *file)
       : symbolKind(k), nameData(name.data), nameSize(name.size), file(file),
-        isUsedInRegularObj(!file || isa<ObjFile>(file)) {}
+        isUsedInRegularObj(!file || isa<ObjFile>(file)),
+        used(!config->deadStrip) {}
 
   Kind symbolKind;
   const char *nameData;
   mutable uint32_t nameSize;
   InputFile *file;
 
 public:
   // True if this symbol was referenced by a regular (non-bitcode) object.
-  bool isUsedInRegularObj;
+  bool isUsedInRegularObj : 1;
+
+  // True if an undefined or shared symbol is used from a live section.
+  bool used : 1;
 };
 
 class Defined : public Symbol {
 public:
   Defined(StringRefZ name, InputFile *file, InputSection *isec, uint64_t value,
           uint64_t size, bool isWeakDef, bool isExternal, bool isPrivateExtern,
-          bool isThumb, bool isReferencedDynamically)
+          bool isThumb, bool isReferencedDynamically, bool noDeadStrip)
       : Symbol(DefinedKind, name, file), isec(isec), value(value), size(size),
         overridesWeakDef(false), privateExtern(isPrivateExtern),
         includeInSymtab(true), thumb(isThumb),
-        referencedDynamically(isReferencedDynamically), weakDef(isWeakDef),
+        referencedDynamically(isReferencedDynamically),
+        noDeadStrip(noDeadStrip), weakDef(isWeakDef),
         external(isExternal) {
     if (isec)
       isec->numRefs++;
   }
 
   bool isWeakDef() const override { return weakDef; }
   bool isExternalWeakDef() const {
     return isWeakDef() && isExternal() && !privateExtern;
public:
   // Whether this symbol should appear in the output symbol table.
   bool includeInSymtab : 1;
   // Only relevant when compiling for Thumb-supporting arm32 archs.
   bool thumb : 1;
   // Symbols marked referencedDynamically won't be removed from the output's
   // symbol table by tools like strip. In theory, this could be set on arbitrary
   // symbols in input object files. In practice, it's used solely for the
   // synthetic __mh_execute_header symbol.
+  // This is information for the static linker, and it's also written to the
+  // output file's symbol table for tools running later (such as `strip`).
   bool referencedDynamically : 1;
+  // Set on symbols that should not be removed by dead code stripping.
+  // Set for example on `__attribute__((used))` globals, or on some Objective-C
+  // metadata. This is information only for the static linker and not written
+  // to the output.
+  bool noDeadStrip : 1;
 
 private:
   const bool weakDef : 1;
   const bool external : 1;
 };
 
 // This enum does double-duty: as a symbol property, it indicates whether & how
 // a dylib symbol is referenced. As a DylibFile property, it indicates the kind

lld/MachO/Symbols.cpp

 std::string lld::toMachOString(const object::Archive::Symbol &b) {
   return demangle(b.getName());
 }
 
 uint64_t Symbol::getStubVA() const { return in.stubs->getVA(stubsIndex); }
 uint64_t Symbol::getGotVA() const { return in.got->getVA(gotIndex); }
 uint64_t Symbol::getTlvVA() const { return in.tlvPointers->getVA(gotIndex); }
 
+bool Symbol::isLive() const {
+  if (isa<DylibSymbol>(this) || isa<Undefined>(this))
+    return used;
+
+  if (auto *d = dyn_cast<Defined>(this)) {
+    // Non-absolute symbols might be alive because their section is
+    // no_dead_strip or live_support. In that case, the section will know
+    // that it's live but `used` might be false. Non-absolute symbols always
+    // have to use the section's `live` bit as source of truth.
+    return d->isec ? d->isec->live : used;
+  }
+
+  assert(!isa<CommonSymbol>(this) &&
+         "replaceCommonSymbols() runs before dead code stripping, and isLive() "
+         "should only be called after dead code stripping");
+
+  // Assume any other kind of symbol is live.
+  return true;
+}
+
 uint64_t Defined::getVA() const {
+  assert(isLive() && "this should only be called for live symbols");
+
   if (isAbsolute())
     return value;
 
   if (!isec->isFinal) {
     // A target arch that does not use thunks ought never ask for
     // the address of a function that has not yet been finalized.
     assert(target->usesThunks());
 

lld/MachO/SyntheticSections.h

 
 // Stores bind opcodes for telling dyld which weak symbols need coalescing.
 // There are two types of entries in this section:
 //
 //   1) Non-weak definitions: This is a symbol definition that weak symbols in
 //   other dylibs should coalesce to.
 //
 //   2) Weak bindings: These tell dyld that a given symbol reference should
-//   coalesce to a non-weak definition if one is found. Note that unlike in the
+//   coalesce to a non-weak definition if one is found. Note that unlike the
 //   entries in the BindingSection, the bindings here only refer to these
 //   symbols by name, but do not specify which dylib to load them from.
 class WeakBindingSection : public LinkEditSection {
 public:
   WeakBindingSection();
   void finalizeContents() override;
   uint64_t getRawSize() const override { return contents.size(); }
   bool isNeeded() const override {

lld/MachO/SyntheticSections.cpp

void StubHelperSection::setup() {
   stubBinder->refState = RefState::Strong;
   in.got->addEntry(stubBinder);
 
   inputSections.push_back(in.imageLoaderCache);
   dyldPrivate =
       make<Defined>("__dyld_private", nullptr, in.imageLoaderCache, 0, 0,
                     /*isWeakDef=*/false,
                     /*isExternal=*/false, /*isPrivateExtern=*/false,
-                    /*isThumb=*/false, /*isReferencedDynamically=*/false);
+                    /*isThumb=*/false, /*isReferencedDynamically=*/false,
+                    /*noDeadStrip=*/true);
 }
 
 ImageLoaderCacheSection::ImageLoaderCacheSection() {
   segname = segment_names::data;
   name = section_names::data;
   uint8_t *arr = bAlloc.Allocate<uint8_t>(target->wordSize);
   memset(arr, 0, target->wordSize);
   data = {arr, target->wordSize};
   align = target->wordSize;
+  live = true;
 }
 
 LazyPointerSection::LazyPointerSection()
     : SyntheticSection(segment_names::data, section_names::lazySymbolPtr) {
   align = target->wordSize;
   flags = S_LAZY_SYMBOL_POINTERS;
 }
 

 
 ExportSection::ExportSection()
     : LinkEditSection(segment_names::linkEdit, section_names::export_) {}
 
 void ExportSection::finalizeContents() {
   trieBuilder.setImageBase(in.header->addr);
   for (const Symbol *sym : symtab->getSymbols()) {
     if (const auto *defined = dyn_cast<Defined>(sym)) {
-      if (defined->privateExtern)
+      if (defined->privateExtern || !defined->isLive())
         continue;
       trieBuilder.addSymbol(*defined);
       hasWeakSymbol = hasWeakSymbol || sym->isWeakDef();
     }
   }
   size = trieBuilder.build();
 }
 
 void ExportSection::writeTo(uint8_t *buf) const { trieBuilder.writeTo(buf); }
 
 FunctionStartsSection::FunctionStartsSection()
     : LinkEditSection(segment_names::linkEdit, section_names::functionStarts) {}
 
 void FunctionStartsSection::finalizeContents() {
   raw_svector_ostream os{contents};
   uint64_t addr = in.header->addr;
   for (const Symbol *sym : symtab->getSymbols()) {
     if (const auto *defined = dyn_cast<Defined>(sym)) {
-      if (!defined->isec || !isCodeSection(defined->isec))
+      if (!defined->isec || !isCodeSection(defined->isec) || !defined->isLive())
         continue;
       // TODO: Add support for thumbs, in that case
       // the lowest bit of nextAddr needs to be set to 1.
       uint64_t nextAddr = defined->getVA();
       uint64_t delta = nextAddr - addr;
       if (delta == 0)
         continue;
       encodeULEB128(delta, os);
for (const std::string &s : config->astPaths) {
     astStab.strx = stringTableSection.addString(s);
     stabs.emplace_back(std::move(astStab));
   }
 
   std::vector<Defined *> symbolsNeedingStabs;
   for (const SymtabEntry &entry :
        concat<SymtabEntry>(localSymbols, externalSymbols)) {
     Symbol *sym = entry.sym;
+    assert(sym->isLive() &&
+           "dead symbols should not be in localSymbols, externalSymbols");
     if (auto *defined = dyn_cast<Defined>(sym)) {
       if (defined->isAbsolute())
         continue;
       InputSection *isec = defined->isec;
       ObjFile *file = dyn_cast_or_null<ObjFile>(isec->file);
       if (!file || !file->compileUnit)
         continue;
       symbolsNeedingStabs.push_back(defined);
auto addSymbol = [&](std::vector<SymtabEntry> &symbols, Symbol *sym) {
     symbols.push_back({sym, strx});
   };
 
   // Local symbols aren't in the SymbolTable, so we walk the list of object
   // files to gather them.
   for (const InputFile *file : inputFiles) {
     if (auto *objFile = dyn_cast<ObjFile>(file)) {
       for (Symbol *sym : objFile->symbols) {
-        if (sym == nullptr)
-          continue;
-        // TODO: when we implement -dead_strip, we should filter out symbols
-        // that belong to dead sections.
-        if (auto *defined = dyn_cast<Defined>(sym)) {
-          if (!defined->isExternal()) {
+        if (auto *defined = dyn_cast_or_null<Defined>(sym)) {
+          if (!defined->isExternal() && defined->isLive()) {
             StringRef name = defined->getName();
             if (!name.startswith("l") && !name.startswith("L"))
               addSymbol(localSymbols, sym);
           }
         }
       }
     }
   }
 
   // __dyld_private is a local symbol too. It's linker-created and doesn't
   // exist in any object file.
   if (Defined *dyldPrivate = in.stubHelper->dyldPrivate)
     addSymbol(localSymbols, dyldPrivate);
 
   for (Symbol *sym : symtab->getSymbols()) {
+    if (!sym->isLive())
+      continue;
     if (auto *defined = dyn_cast<Defined>(sym)) {
       if (!defined->includeInSymtab)
         continue;
       assert(defined->isExternal());
       if (defined->privateExtern)
         addSymbol(localSymbols, defined);
       else
         addSymbol(externalSymbols, defined);

lld/MachO/UnwindInfoSection.cpp

 // all sizes. Therefore, we don't even bother implementing the regular
 // non-compressed format. Time will tell if anyone in the field ever
 // overflows the 127-encodings limit.
 //
 // Refer to the definition of unwind_info_section_header in
 // compact_unwind_encoding.h for an overview of the format we are encoding
 // here.
 
-// TODO(gkm): prune __eh_frame entries superseded by __unwind_info
+// TODO(gkm): prune __eh_frame entries superseded by __unwind_info, PR50410
 // TODO(gkm): how do we align the 2nd-level pages?
 
 using EncodingMap = llvm::DenseMap<compact_unwind_encoding_t, size_t>;
 
 template <class Ptr> struct CompactUnwindEntry {
   Ptr functionAddress;
   uint32_t functionLength;
   compact_unwind_encoding_t encoding;

 // reside in the GOT and must be treated specially.
 template <class Ptr>
 void UnwindInfoSectionImpl<Ptr>::prepareRelocations(InputSection *isec) {
   assert(isec->segname == segment_names::ld &&
          isec->name == section_names::compactUnwind);
   assert(!isec->shouldOmitFromOutput() &&
          "__compact_unwind section should not be omitted");
 
+  // FIXME: This could skip relocations for CompactUnwindEntries that
+  // point to dead-stripped functions. That might save some amount of
+  // work. But since there are usually just few personality functions
+  // that are referenced from many places, at least some of them likely
+  // live, it wouldn't reduce number of got entries.
   for (Reloc &r : isec->relocs) {
     assert(target->hasAttr(r.type, RelocAttrBits::UNSIGNED));
     if (r.offset % sizeof(CompactUnwindEntry<Ptr>) !=
         offsetof(CompactUnwindEntry<Ptr>, personality))
       continue;
 
     if (auto *s = r.referent.dyn_cast<Symbol *>()) {
       if (auto *undefined = dyn_cast<Undefined>(s)) {
if (auto *s = r.referent.dyn_cast<Symbol *>()) {
         continue;
       }
       assert(isa<DylibSymbol>(s));
       in.got->addEntry(s);
       continue;
     }
 
     if (auto *referentIsec = r.referent.dyn_cast<InputSection *>()) {
-      assert(!referentIsec->shouldOmitFromOutput());
+      assert(!referentIsec->isCoalescedWeak());
 
       // Personality functions can be referenced via section relocations
       // if they live in the same object file. Create placeholder synthetic
       // symbols for them in the GOT.
       Symbol *&s = personalityTable[{referentIsec, r.addend}];
       if (s == nullptr) {
+        // This runs after dead stripping, so the noDeadStrip argument does not
+        // matter.
         s = make<Defined>("<internal>", /*file=*/nullptr, referentIsec,
                           r.addend, /*size=*/0, /*isWeakDef=*/false,
                           /*isExternal=*/false, /*isPrivateExtern=*/false,
-                          /*isThumb=*/false, /*isReferencedDynamically=*/false);
+                          /*isThumb=*/false, /*isReferencedDynamically=*/false,
+                          /*noDeadStrip=*/false);
         in.got->addEntry(s);
       }
       r.referent = s;
       r.addend = 0;
     }
   }
 }
 

lld/MachO/Writer.cpp

for (InputSection *isec : inputSections) {
     }
   }
 }
 
 void Writer::scanSymbols() {
   TimeTraceScope timeScope("Scan symbols");
   for (const Symbol *sym : symtab->getSymbols()) {
     if (const auto *defined = dyn_cast<Defined>(sym)) {
-      if (defined->overridesWeakDef)
+      if (defined->overridesWeakDef && defined->isLive())
         in.weakBinding->addNonWeakDefinition(defined);
     } else if (const auto *dysym = dyn_cast<DylibSymbol>(sym)) {
+      // This branch intentionally doesn't check isLive().
       if (dysym->isDynamicLookup())
         continue;
       dysym->getFile()->refState =
           std::max(dysym->getFile()->refState, dysym->refState);
     }
   }
 }
 

lld/test/MachO/Inputs/MacOSX.sdk/usr/lib/libc++abi.tbd

 --- !tapi-tbd-v3
 archs:            [ i386, x86_64, arm64 ]
 uuids:            [ 'i386: 00000000-0000-0000-0000-000000000000', 'x86_64: 00000000-0000-0000-0000-000000000001', 'arm64: 00000000-0000-0000-0000-000000000002' ]
 platform:         macosx
 install-name:     '/usr/lib/libc++abi.dylib'
 current-version:  1281
 exports:
   - archs:        [ i386, x86_64, arm64 ]
-    symbols:      [ ___gxx_personality_v0 ]
+    symbols:      [ ___cxa_allocate_exception, ___cxa_begin_catch, ___cxa_end_catch, ___cxa_throw, ___gxx_personality_v0, __ZTIi ]
 ...

lld/test/MachO/dead-strip.s

+# REQUIRES: x86
+
+# 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
+# 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
+# EXEC-NEXT:   {{.*}} l {{.*}} _ref_local
+# EXEC-NEXT:   {{.*}} l {{.*}} _ref_from_no_dead_strip_globl
+# EXEC-NEXT:   {{.*}} l {{.*}} _no_dead_strip_local
+# EXEC-NEXT:   {{.*}} l {{.*}} _ref_from_no_dead_strip_local
+# EXEC-NEXT:   {{.*}} l {{.*}} _ref_private_extern_u
+# EXEC-NEXT:   {{.*}} l {{.*}} _main
+# EXEC-NEXT:   {{.*}} l {{.*}} _ref_private_extern
+# EXEC-NEXT:   {{.*}} g {{.*}} _ref_com
+# EXEC-NEXT:   {{.*}} g {{.*}} _no_dead_strip_globl
+# EXEC-NEXT:   {{.*}} g {{.*}} __mh_execute_header
+# EXECDATA-LABEL: Indirect symbols
+# EXECDATA-NEXT:  name
+# 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
+
+# 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
+
+## Absolute symbol handling.
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-macos \
+# RUN:     %t/abs.s -o %t/abs.o
+# RUN: %lld -lSystem -dead_strip %t/abs.o -o %t/abs
+# RUN: llvm-objdump --macho --syms --exports-trie %t/abs | \
+# RUN:     FileCheck --check-prefix=ABS %s
+#ABS-LABEL: SYMBOL TABLE:
+#ABS-NEXT:  {{.*}} g {{.*}} _main
+#ABS-NEXT:  {{.*}} g *ABS* _abs1
+#ABS-NEXT:  {{.*}} g {{.*}} __mh_execute_header
+#ABS-LABEL: Exports trie:
+#ABS-NEXT: {{.*}}  __mh_execute_header
+#ABS-NEXT: {{.*}}  _main
+#ABS-NEXT: {{.*}}  _abs1 [absolute]
+
+## Check that symbols from -exported_symbol(s_list) are preserved.
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-macos \
+# RUN:     %t/exported-symbol.s -o %t/exported-symbol.o
+# RUN: %lld -lSystem -dead_strip -exported_symbol _my_exported_symbol \
+# RUN:     %t/exported-symbol.o -o %t/exported-symbol
+# RUN: llvm-objdump --syms %t/exported-symbol | \
+# RUN:     FileCheck --check-prefix=EXPORTEDSYMBOL --implicit-check-not _unref %s
+# EXPORTEDSYMBOL-LABEL: SYMBOL TABLE:
+# EXPORTEDSYMBOL-NEXT:   {{.*}} l {{.*}} _main
+# EXPORTEDSYMBOL-NEXT:   {{.*}} l {{.*}} __mh_execute_header
+# EXPORTEDSYMBOL-NEXT:   {{.*}} g {{.*}} _my_exported_symbol
+
+## Check that mod_init_funcs and mod_term_funcs are not stripped.
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-macos \
+# RUN:     %t/mod-funcs.s -o %t/mod-funcs.o
+# RUN: %lld -lSystem -dead_strip %t/mod-funcs.o -o %t/mod-funcs
+# RUN: llvm-objdump --syms %t/mod-funcs | \
+# RUN:     FileCheck --check-prefix=MODFUNCS --implicit-check-not _unref %s
+# MODFUNCS-LABEL: SYMBOL TABLE:
+# MODFUNCS-NEXT:   {{.*}} l {{.*}} _ref_from_init
+# MODFUNCS-NEXT:   {{.*}} l {{.*}} _ref_init
+# MODFUNCS-NEXT:   {{.*}} l {{.*}} _ref_from_term
+# MODFUNCS-NEXT:   {{.*}} l {{.*}} _ref_term
+# MODFUNCS-NEXT:   {{.*}} g {{.*}} _main
+# MODFUNCS-NEXT:   {{.*}} g {{.*}} __mh_execute_header
+
+## Check that DylibSymbols in dead subsections are stripped: They should
+## not be in the import table and should have no import stubs.
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-macos \
+# RUN:     %t/dylib.s -o %t/dylib.o
+# RUN: %lld -dylib -dead_strip %t/dylib.o -o %t/dylib.dylib
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-macos \
+# RUN:     %t/strip-dylib-ref.s -o %t/strip-dylib-ref.o
+# RUN: %lld -lSystem -dead_strip %t/strip-dylib-ref.o %t/dylib.dylib \
+# RUN:     -o %t/strip-dylib-ref -U _ref_undef_fun -U _unref_undef_fun
+# RUN: llvm-objdump --syms --bind --lazy-bind --weak-bind %t/strip-dylib-ref | \
+# RUN:     FileCheck --check-prefix=STRIPDYLIB --implicit-check-not _unref %s
+# STRIPDYLIB:      SYMBOL TABLE:
+# STRIPDYLIB-NEXT: {{.*}} l {{.*}} __dyld_private
+# STRIPDYLIB-NEXT: {{.*}} g {{.*}} _main
+# STRIPDYLIB-NEXT: {{.*}} g {{.*}} __mh_execute_header
+# STRIPDYLIB-NEXT: {{.*}} *UND* _ref_undef_fun
+# STRIPDYLIB-NEXT: {{.*}} *UND* dyld_stub_binder
+# STRIPDYLIB-NEXT: {{.*}} *UND* _ref_dylib_fun
+# STRIPDYLIB:      Bind table:
+# STRIPDYLIB:      Lazy bind table:
+# STRIPDYLIB:      __DATA   __la_symbol_ptr {{.*}} flat-namespace _ref_undef_fun
+# STRIPDYLIB:      __DATA   __la_symbol_ptr {{.*}} dylib _ref_dylib_fun
+# STRIPDYLIB:      Weak bind table:
+## Stubs smoke check: There should be two stubs entries, not four, but we
+## don't verify that they belong to _ref_undef_fun and _ref_dylib_fun.
+# RUN: llvm-objdump -d --section=__stubs --section=__stub_helper \
+# RUN:     %t/strip-dylib-ref |FileCheck --check-prefix=STUBS %s
+# STUBS-LABEL: <__stubs>:
+# STUBS-NEXT:  jmpq
+# STUBS-NEXT:  jmpq
+# STUBS-NOT:   jmpq
+# STUBS-LABEL: <__stub_helper>:
+# STUBS:  pushq $0
+# STUBS:  jmp
+# STUBS:  jmp
+# STUBS-NOT:  jmp
+## An undefined symbol referenced from a dead-stripped function shouldn't
+## produce a diagnostic:
+# RUN: %lld -lSystem -dead_strip %t/strip-dylib-ref.o %t/dylib.dylib \
+# RUN:     -o %t/strip-dylib-ref -U _ref_undef_fun
+
+## S_ATTR_LIVE_SUPPORT tests.
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-macos \
+# RUN:     %t/live-support.s -o %t/live-support.o
+# RUN: %lld -lSystem -dead_strip %t/live-support.o %t/dylib.dylib \
+# RUN:     -U _ref_undef_fun -U _unref_undef_fun -o %t/live-support
+# RUN: llvm-objdump --syms %t/live-support | \
+# RUN:     FileCheck --check-prefix=LIVESUPP --implicit-check-not _unref %s
+# LIVESUPP-LABEL: SYMBOL TABLE:
+# LIVESUPP-NEXT:   {{.*}} l {{.*}} _ref_ls_fun_fw
+# LIVESUPP-NEXT:   {{.*}} l {{.*}} _ref_ls_fun_bw
+# LIVESUPP-NEXT:   {{.*}} l {{.*}} _ref_ls_dylib_fun
+# LIVESUPP-NEXT:   {{.*}} l {{.*}} _ref_ls_undef_fun
+# LIVESUPP-NEXT:   {{.*}} l {{.*}} __dyld_private
+# LIVESUPP-NEXT:   {{.*}} g {{.*}} _main
+# LIVESUPP-NEXT:   {{.*}} g {{.*}} _bar
+# LIVESUPP-NEXT:   {{.*}} g {{.*}} _foo
+# LIVESUPP-NEXT:   {{.*}} g {{.*}} __mh_execute_header
+# LIVESUPP-NEXT:   *UND* _ref_undef_fun
+# LIVESUPP-NEXT:   *UND* dyld_stub_binder
+# LIVESUPP-NEXT:   *UND* _ref_dylib_fun
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-macos \
+# RUN:     %t/live-support-iterations.s -o %t/live-support-iterations.o
+# RUN: %lld -lSystem -dead_strip %t/live-support-iterations.o \
+# RUN:     -o %t/live-support-iterations
+# RUN: llvm-objdump --syms %t/live-support-iterations | \
+# RUN:     FileCheck --check-prefix=LIVESUPP2 --implicit-check-not _unref %s
+# LIVESUPP2-LABEL: SYMBOL TABLE:
+# LIVESUPP2-NEXT:   {{.*}} l {{.*}} _bar
+# LIVESUPP2-NEXT:   {{.*}} l {{.*}} _foo_refd
+# LIVESUPP2-NEXT:   {{.*}} l {{.*}} _bar_refd
+# LIVESUPP2-NEXT:   {{.*}} l {{.*}} _baz
+# LIVESUPP2-NEXT:   {{.*}} l {{.*}} _baz_refd
+# LIVESUPP2-NEXT:   {{.*}} l {{.*}} _foo
+# LIVESUPP2-NEXT:   {{.*}} g {{.*}} _main
+# LIVESUPP2-NEXT:   {{.*}} g {{.*}} __mh_execute_header
+
+## Dead stripping should not remove the __TEXT,__unwind_info
+## and __TEXT,__gcc_except_tab functions, but it should still
+## remove the unreferenced function __Z5unref.
+## The reference to ___gxx_personality_v0 should also not be
+## stripped.
+## (Need to use darwin19.0.0 to make -mc emit __LD,__compact_unwind.)
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin19.0.0 \
+# RUN:     %t/unwind.s -o %t/unwind.o
+# RUN: %lld -lc++ -lSystem -dead_strip %t/unwind.o -o %t/unwind
+# RUN: llvm-objdump --syms %t/unwind | \
+# RUN:     FileCheck --check-prefix=UNWIND --implicit-check-not unref %s
+# RUN: llvm-otool -l %t/unwind | grep -q 'sectname __unwind_info'
+# RUN: llvm-otool -l %t/unwind | grep -q 'sectname __gcc_except_tab'
+# UNWIND-LABEL: SYMBOL TABLE:
+# UNWIND-NEXT: {{.*}} l O __TEXT,__gcc_except_tab GCC_except_table1
+# UNWIND-NEXT: {{.*}} l O __DATA,__data __dyld_private
+# UNWIND-NEXT: {{.*}} g F __TEXT,__text _main
+# UNWIND-NEXT: {{.*}} g F __TEXT,__text __mh_execute_header
+# UNWIND-NEXT: *UND* ___cxa_allocate_exception
+# UNWIND-NEXT: *UND* ___cxa_end_catch
+# UNWIND-NEXT: *UND* __ZTIi
+# UNWIND-NEXT: *UND* ___cxa_throw
+# UNWIND-NEXT: *UND* ___gxx_personality_v0
+# UNWIND-NEXT: *UND* ___cxa_begin_catch
+# UNWIND-NEXT: *UND* dyld_stub_binder
+
+## If a dead stripped function has a strong ref to a dylibsymbol but
+## a live function only a weak ref, the dylib is still not a WEAK_DYLIB.
+## This matches ld64.
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-macos \
+# RUN:     %t/weak-ref.s -o %t/weak-ref.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-macos \
+# RUN:     %t/strong-dead-ref.s -o %t/strong-dead-ref.o
+# RUN: %lld -lSystem -dead_strip %t/weak-ref.o %t/strong-dead-ref.o \
+# RUN:     %t/dylib.dylib -o %t/weak-ref
+# RUN: llvm-otool -l %t/weak-ref | FileCheck -DDIR=%t --check-prefix=WEAK %s
+# WEAK:          cmd LC_LOAD_DYLIB
+# WEAK-NEXT: cmdsize
+# WEAK-NEXT:    name /usr/lib/libSystem.dylib
+# WEAK:          cmd LC_LOAD_DYLIB
+# WEAK-NEXT: cmdsize
+# WEAK-NEXT:    name [[DIR]]/dylib.dylib
+
+## A strong symbol that would override a weak import does not emit the
+## "this overrides a weak import" opcode if it is dead-stripped.
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-macos \
+# RUN:     %t/weak-dylib.s -o %t/weak-dylib.o
+# RUN: %lld -dylib -dead_strip %t/weak-dylib.o -o %t/weak-dylib.dylib
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-macos \
+# RUN:     %t/dead-weak-override.s -o %t/dead-weak-override.o
+# RUN: %lld -dead_strip %t/dead-weak-override.o %t/weak-dylib.dylib \
+# RUN:     -o %t/dead-weak-override
+# RUN: llvm-objdump --macho --weak-bind --private-header \
+# RUN:     %t/dead-weak-override | FileCheck --check-prefix=DEADWEAK %s
+# DEADWEAK-NOT: WEAK_DEFINES
+# DEADWEAK: Weak bind table:
+# DEADWEAK: segment  section            address     type       addend   symbol
+# DEADWEAK-NOT: strong              _weak_in_dylib
+
+## Stripped symbols should not be in the debug info stabs entries.
+# RUN: llvm-mc -g -filetype=obj -triple=x86_64-apple-macos \
+# RUN:     %t/debug.s -o %t/debug.o
+# RUN: %lld -lSystem -dead_strip %t/debug.o -o %t/debug
+# RUN: dsymutil -s %t/debug | FileCheck --check-prefix=EXECSTABS %s
+# EXECSTABS-NOT: N_FUN {{.*}} '_unref'
+# EXECSTABS:     N_FUN {{.*}} '_main'
+# EXECSTABS-NOT: N_FUN {{.*}} '_unref'
+
+#--- basics.s
+.comm _ref_com, 1
+.comm _unref_com, 1
+
+.section __DATA,__unref_section
+_unref_data:
+  .quad 4
+
+l_unref_data:
+  .quad 5
+
+## Referenced by no_dead_strip == S_ATTR_NO_DEAD_STRIP
+.section __DATA,__ref_section,regular,no_dead_strip
+
+## Referenced because in no_dead_strip section.
+_ref_data:
+  .quad 4
+
+## This is a local symbol so it's not in the symbol table, but
+## it is still in the section data.
+l_ref_data:
+  .quad 5
+
+.text
+
+# Exported symbols should not be stripped from dylibs
+# or bundles, but they should be stripped from executables.
+.globl _unref_extern
+_unref_extern:
+  callq _ref_local
+  retq
+
+# Unreferenced local symbols should be stripped.
+_unref_local:
+  retq
+
+# Same for unreferenced private externs.
+.globl _unref_private_extern
+.private_extern _unref_private_extern
+_unref_private_extern:
+  # This shouldn't create an indirect symbol since it's
+  # a reference from a dead function.
+  movb _unref_com@GOTPCREL(%rip), %al
+  retq
+
+# Referenced local symbols should not be stripped.
+_ref_local:
+  callq _ref_private_extern
+  retq
+
+# Same for referenced private externs.
+# This one is referenced by a relocation.
+.globl _ref_private_extern
+.private_extern _ref_private_extern
+_ref_private_extern:
+  retq
+
+# This one is referenced by a -u flag.
+.globl _ref_private_extern_u
+.private_extern _ref_private_extern_u
+_ref_private_extern_u:
+  retq
+
+# Entry point should not be stripped for executables, even if hidden.
+# For shared libraries this is stripped since it's just a regular hidden
+# symbol there.
+.globl _main
+.private_extern _main
+_main:
+  movb _ref_com@GOTPCREL(%rip), %al
+  callq _ref_local
+  retq
+
+# Things marked no_dead_strip should not be stripped either.
+# (clang emits this e.g. for `__attribute__((used))` globals.)
+# Both for .globl symbols...
+.globl _no_dead_strip_globl
+.no_dead_strip _no_dead_strip_globl
+_no_dead_strip_globl:
+  callq _ref_from_no_dead_strip_globl
+  retq
+_ref_from_no_dead_strip_globl:
+  retq
+
+# ...and for locals.
+.no_dead_strip _no_dead_strip_local
+_no_dead_strip_local:
+  callq _ref_from_no_dead_strip_local
+  retq
+_ref_from_no_dead_strip_local:
+  retq
+
+.subsections_via_symbols
+
+#--- exported-symbol.s
+.text
+
+.globl _unref_symbol
+_unref_symbol:
+  retq
+
+.globl _my_exported_symbol
+_my_exported_symbol:
+  retq
+
+.globl _main
+_main:
+  retq
+
+.subsections_via_symbols
+
+#--- abs.s
+.globl _abs1, _abs2, _abs3
+
+.no_dead_strip _abs1
+_abs1 = 1
+_abs2 = 2
+_abs3 = 3
+
+.section __DATA,__foo,regular,no_dead_strip
+# Absolute symbols are not in a section, so the no_dead_strip
+# on the section above has no effect.
+.globl _abs4
+_abs4 = 4
+
+.text
+.globl _main
+_main:
+  # This is relaxed away, so there's no relocation here and
+  # _abs3 isn't in the exported symbol table.
+  mov _abs3, %rax
+  retq
+
+.subsections_via_symbols
+
+#--- mod-funcs.s
+## Roughly based on `clang -O2 -S` output for `struct A { A(); ~A(); }; A a;`
+## for mod_init_funcs. mod_term_funcs then similar to that.
+.section __TEXT,__StaticInit,regular,pure_instructions
+
+__unref:
+  retq
+
+_ref_from_init:
+  retq
+
+_ref_init:
+  callq _ref_from_init
+  retq
+
+_ref_from_term:
+  retq
+
+_ref_term:
+  callq _ref_from_term
+  retq
+
+.globl _main
+_main:
+  retq
+
+.section __DATA,__mod_init_func,mod_init_funcs
+.quad _ref_init
+
+.section __DATA,__mod_term_func,mod_term_funcs
+.quad _ref_term
+
+.subsections_via_symbols
+
+#--- dylib.s
+.text
+
+.globl _ref_dylib_fun
+_ref_dylib_fun:
+  retq
+
+.globl _unref_dylib_fun
+_unref_dylib_fun:
+  retq
+
+.subsections_via_symbols
+
+#--- strip-dylib-ref.s
+.text
+
+_unref:
+  callq _ref_dylib_fun
+  callq _unref_dylib_fun
+  callq _ref_undef_fun
+  callq _unref_undef_fun
+  retq
+
+.globl _main
+_main:
+  callq _ref_dylib_fun
+  callq _ref_undef_fun
+  retq
+
+.subsections_via_symbols
+
+#--- live-support.s
+## In practice, live_support is used for instruction profiling
+## data and asan. (Also for __eh_frame, but that needs special handling
+## in the linker anyways.)
+## This test isn't based on anything happening in real code though.
+.section __TEXT,__ref_ls_fw,regular,live_support
+_ref_ls_fun_fw:
+  # This is called by _main and is kept alive by normal
+  # forward liveness propagation, The live_support attribute
+  # does nothing in this case.
+  retq
+
+.section __TEXT,__unref_ls_fw,regular,live_support
+_unref_ls_fun_fw:
+  retq
+
+.section __TEXT,__ref_ls_bw,regular,live_support
+_ref_ls_fun_bw:
+  # This _calls_ something that's alive but isn't referenced itself. This is
+  # kept alive only due to this being in a live_support section.
+  callq _foo
+
+  # _bar on the other hand is kept alive since it's called from here.
+  callq _bar
+  retq
+
+## Kept alive by a live symbol form a dynamic library.
+_ref_ls_dylib_fun:
+  callq _ref_dylib_fun
+  retq
+
+## Kept alive by a live undefined symbol.
+_ref_ls_undef_fun:
+  callq _ref_undef_fun
+  retq
+
+## All symbols in this live_support section reference dead symbols
+## and are hence dead themselves.
+.section __TEXT,__unref_ls_bw,regular,live_support
+_unref_ls_fun_bw:
+  callq _unref
+  retq
+
+_unref_ls_dylib_fun_bw:
+  callq _unref_dylib_fun
+  retq
+
+_unref_ls_undef_fun_bw:
+  callq _unref_undef_fun
+  retq
+
+.text
+.globl _unref
+_unref:
+  retq
+
+.globl _bar
+_bar:
+  retq
+
+.globl _foo
+_foo:
+  callq _ref_ls_fun_fw
+  retq
+
+.globl _main
+_main:
+  callq _ref_ls_fun_fw
+  callq _foo
+  callq _ref_dylib_fun
+  callq _ref_undef_fun
+  retq
+
+.subsections_via_symbols
+
+#--- live-support-iterations.s
+.section __TEXT,_ls,regular,live_support
+
+## This is a live_support subsection that only becomes
+## live after _foo below is processed. This means the algorithm of
+## 1. mark things reachable from gc roots live
+## 2. go through live sections and mark the ones live pointing to
+##    live symbols or sections
+## needs more than one iteration, since _bar won't be live when step 2
+## runs for the first time.
+## (ld64 gets this wrong -- it has different output based on if _bar is
+## before _foo or after it.)
+_bar:
+  callq _foo_refd
+  callq _bar_refd
+  retq
+
+## Same here. This is maybe more interesting since it references a live_support
+## symbol instead of a "normal" symbol.
+_baz:
+  callq _foo_refd
+  callq _baz_refd
+  retq
+
+_foo:
+  callq _main
+  callq _foo_refd
+  retq
+
+## Test no_dead_strip on a symbol in a live_support section.
+## ld64 ignores this, but that doesn't look intentional. So lld honors it.
+# do better.
+.no_dead_strip
+_quux:
+  retq
+
+
+.text
+.globl _main
+_main:
+  movq $0, %rax
+  retq
+
+_foo_refd:
+  retq
+
+_bar_refd:
+  retq
+
+_baz_refd:
+  retq
+
+.subsections_via_symbols
+
+#--- unwind.s
+## This is the output of `clang -O2 -S throw.cc` where throw.cc
+## looks like this:
+##     void unref() {}
+##     int main() {
+##       try {
+##         throw 0;
+##       } catch (int i) {
+##         return i;
+##       }
+##     }
+.section __TEXT,__text,regular,pure_instructions
+
+.globl __Z5unrefv
+.p2align 4, 0x90
+__Z5unrefv:
+.cfi_startproc
+  pushq %rbp
+  .cfi_def_cfa_offset 16
+  .cfi_offset %rbp, -16
+  movq %rsp, %rbp
+  .cfi_def_cfa_register %rbp
+  popq %rbp
+  retq
+  .cfi_endproc
+
+.globl _main
+.p2align 4, 0x90
+_main:
+Lfunc_begin0:
+  .cfi_startproc
+  .cfi_personality 155, ___gxx_personality_v0
+  .cfi_lsda 16, Lexception0
+  pushq %rbp
+  .cfi_def_cfa_offset 16
+  .cfi_offset %rbp, -16
+  movq %rsp, %rbp
+  .cfi_def_cfa_register %rbp
+  pushq %rbx
+  pushq %rax
+  .cfi_offset %rbx, -24
+  movl $4, %edi
+  callq ___cxa_allocate_exception
+  movl $0, (%rax)
+Ltmp0:
+  movq __ZTIi@GOTPCREL(%rip), %rsi
+  movq %rax, %rdi
+  xorl %edx, %edx
+  callq ___cxa_throw
+Ltmp1:
+  ud2
+LBB1_2:
+Ltmp2:
+  movq %rax, %rdi
+  callq ___cxa_begin_catch
+  movl (%rax), %ebx
+  callq ___cxa_end_catch
+  movl %ebx, %eax
+  addq $8, %rsp
+  popq %rbx
+  popq %rbp
+  retq
+Lfunc_end0:
+.cfi_endproc
+
+.section __TEXT,__gcc_except_tab
+.p2align 2
+GCC_except_table1:
+Lexception0:
+  .byte 255                     ## @LPStart Encoding = omit
+  .byte 155                     ## @TType Encoding = indirect pcrel sdata4
+  .uleb128 Lttbase0-Lttbaseref0
+Lttbaseref0:
+  .byte 1                       ## Call site Encoding = uleb128
+  .uleb128 Lcst_end0-Lcst_begin0
+Lcst_begin0:
+  .uleb128 Lfunc_begin0-Lfunc_begin0 ## >> Call Site 1 <<
+  .uleb128 Ltmp0-Lfunc_begin0   ##   Call between Lfunc_begin0 and Ltmp0
+  .byte 0                       ##     has no landing pad
+  .byte 0                       ##   On action: cleanup
+  .uleb128 Ltmp0-Lfunc_begin0   ## >> Call Site 2 <<
+  .uleb128 Ltmp1-Ltmp0          ##   Call between Ltmp0 and Ltmp1
+  .uleb128 Ltmp2-Lfunc_begin0   ##     jumps to Ltmp2
+  .byte 1                       ##   On action: 1
+  .uleb128 Ltmp1-Lfunc_begin0   ## >> Call Site 3 <<
+  .uleb128 Lfunc_end0-Ltmp1     ##   Call between Ltmp1 and Lfunc_end0
+  .byte 0                       ##     has no landing pad
+  .byte 0                       ##   On action: cleanup
+Lcst_end0:
+  .byte 1                       ## >> Action Record 1 <<
+                                         ##   Catch TypeInfo 1
+  .byte 0                       ##   No further actions
+  .p2align 2
+                                ## >> Catch TypeInfos <<
+  .long __ZTIi@GOTPCREL+4       ## TypeInfo 1
+Lttbase0:
+  .p2align 2
+                                ## -- End function
+.subsections_via_symbols
+
+#--- weak-ref.s
+.text
+.weak_reference _ref_dylib_fun
+.globl _main
+_main:
+  callq _ref_dylib_fun
+  retq
+
+.subsections_via_symbols
+
+#--- strong-dead-ref.s
+.text
+.globl _unref_dylib_fun
+_unref:
+  callq _unref_dylib_fun
+  retq
+
+.subsections_via_symbols
+
+#--- weak-dylib.s
+.text
+.globl _weak_in_dylib
+.weak_definition _weak_in_dylib
+_weak_in_dylib:
+  retq
+
+.subsections_via_symbols
+
+#--- dead-weak-override.s
+
+## Overrides the _weak_in_dylib symbol in weak-dylib, but is dead stripped.
+.text
+
+#.no_dead_strip _weak_in_dylib
+.globl _weak_in_dylib
+_weak_in_dylib:
+  retq
+
+.globl _main
+_main:
+  retq
+
+.subsections_via_symbols
+
+#--- debug.s
+.text
+.globl _unref
+_unref:
+  retq
+
+.globl _main
+_main:
+  retq
+
+.subsections_via_symbols

lld/test/MachO/mh-header-link.s

 # REQUIRES: x86
 
 ## This tests that we can link against these synthetic symbols even
 ## if they are not in the symbol table.
 
 # RUN: rm -rf %t; split-file %s %t
 
 ## Test that in a dylib, we can link against __mh_dylib_header
 ## (but not in other types of files)
 
 # RUN: llvm-mc %t/dylib.s -triple=x86_64-apple-macos10.15 -filetype=obj -o %t/dylib.o
-# RUN: %lld -pie -dylib %t/dylib.o -o %t/dylib.out
+# RUN: %lld -pie -dylib -dead_strip %t/dylib.o -o %t/dylib.out
 # RUN: llvm-objdump -m --syms %t/dylib.out | FileCheck %s --check-prefix DYLIB
 
 # RUN: not %lld -pie -o /dev/null %t/dylib.o 2>&1 | FileCheck %s --check-prefix ERR-DYLIB
 
 # DYLIB:      SYMBOL TABLE:
 # DYLIB-NEXT: {{[0-9a-f]+}} g     F __TEXT,__text _main
 # DYLIB-NEXT-EMPTY:
 # ERR-DYLIB: error: undefined symbol: __mh_dylib_header
 
 ## Test that in an executable, we can link against __mh_execute_header
 # RUN: llvm-mc %t/main.s -triple=x86_64-apple-macos10.15 -filetype=obj -o %t/exec.o
-# RUN: %lld -pie %t/exec.o -o %t/exec.out
+# RUN: %lld -pie -dead_strip -lSystem %t/exec.o -o %t/exec.out
 
 ## But it would be an error trying to reference __mh_execute_header in a dylib
 # RUN: not %lld -pie -o /dev/null -dylib %t/exec.o 2>&1 | FileCheck %s --check-prefix ERR-EXEC
 
 # ERR-EXEC: error: undefined symbol: __mh_execute_header
 
 #--- main.s
 .text
 .globl _main
 _main:
  mov __mh_execute_header@GOTPCREL(%rip), %rax
  ret
 
+.subsections_via_symbols
 #--- dylib.s
 .text
 .globl _main
 _main:
  mov __mh_dylib_header@GOTPCREL(%rip), %rax
  ret
+
+.subsections_via_symbols

lld/test/MachO/sectcreate.s

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %s -o %t.o
 # RUN: echo "-sectcreate 1.1" >%t1
 # RUN: echo "-sectcreate 1.2" >%t2
 # RUN: echo "-sectcreate 2" >%t3
 # RUN: %lld \
 # RUN:     -sectcreate SEG SEC1 %t1 \
 # RUN:     -segcreate SEG SEC2 %t3 \
 # RUN:     -sectcreate SEG SEC1 %t2 \
 # RUN:     -o %t %t.o
 # RUN: llvm-objdump -s %t | FileCheck %s
 
+## -dead_strip does not strip -sectcreate sections,
+## but also doesn't set S_ATTR_NO_DEAD_STRIP on them.
+# RUN: %lld -dead_strip \
+# RUN:     -sectcreate SEG SEC1 %t1 \
+# RUN:     -segcreate SEG SEC2 %t3 \
+# RUN:     -sectcreate SEG SEC1 %t2 \
+# RUN:     -o %t %t.o
+# RUN: llvm-objdump -s %t | FileCheck --check-prefix=STRIPPED %s
+# RUN: llvm-readobj --sections %t | FileCheck --check-prefix=STRIPPEDSEC %s
+
 # CHECK: Contents of section __TEXT,__text:
 # CHECK: Contents of section __DATA,__data:
 # CHECK: my string!.
 # CHECK: Contents of section SEG,SEC1:
 # CHECK: -sectcreate 1.1.
 # CHECK: -sectcreate 1.2.
 # CHECK: Contents of section SEG,SEC2:
 # CHECK: -sectcreate 2.
 
+# STRIPPED: Contents of section __TEXT,__text:
+# STRIPPED-NOT: Contents of section __DATA,__data:
+# STRIPPED-NOT: my string!.
+# STRIPPED: Contents of section SEG,SEC1:
+# STRIPPED: -sectcreate 1.1.
+# STRIPPED: -sectcreate 1.2.
+# STRIPPED: Contents of section SEG,SEC2:
+# STRIPPED: -sectcreate 2.
+
+# STRIPPEDSEC-NOT: NoDeadStrip
+
 .text
 .global _main
 _main:
   mov $0, %eax
   ret
 
 .data
 .global my_string
 my_string:
   .string "my string!"
+
+.subsections_via_symbols

llvm/utils/gn/secondary/lld/MachO/BUILD.gn

sources = [
     "Driver.cpp",
     "DriverUtils.cpp",
     "Dwarf.cpp",
     "ExportTrie.cpp",
     "InputFiles.cpp",
     "InputSection.cpp",
     "LTO.cpp",
     "MapFile.cpp",
+    "MarkLive.cpp",
     "ObjC.cpp",
     "OutputSection.cpp",
     "OutputSegment.cpp",
     "Relocations.cpp",
     "SymbolTable.cpp",
     "Symbols.cpp",
     "SyntheticSections.cpp",
     "Target.cpp",
     "UnwindInfoSection.cpp",
     "Writer.cpp",
   ]
 }