macho: move GC code into dead_strip.zig module

Implement marking live atoms that reference other live atoms if
required by the compiler (via section attribute).

4 files changed, 325 insertions, 284 deletions

diff --git a/src/link/MachO.zig b/src/link/MachO.zig
index 49f4c34bb4..4c344c6260 100644
--- a/src/link/MachO.zig
+++ b/src/link/MachO.zig
@@ -16,6 +16,7 @@ const meta = std.meta;
 const aarch64 = @import("../arch/aarch64/bits.zig");
 const bind = @import("MachO/bind.zig");
 const codegen = @import("../codegen.zig");
+const dead_strip = @import("MachO/dead_strip.zig");
 const link = @import("../link.zig");
 const llvm_backend = @import("../codegen/llvm.zig");
 const target_util = @import("../target.zig");
@@ -709,7 +710,7 @@ fn linkOneShot(self: *MachO, comp: *Compilation, prog_node: *std.Progress.Node)
     const is_dyn_lib = self.base.options.link_mode == .Dynamic and is_lib;
     const is_exe_or_dyn_lib = is_dyn_lib or self.base.options.output_mode == .Exe;
     const stack_size = self.base.options.stack_size_override orelse 0;
-    const dead_strip = self.base.options.gc_sections orelse false;
+    const gc_sections = self.base.options.gc_sections orelse false;
 
     const id_symlink_basename = "zld.id";
 
@@ -741,7 +742,7 @@ fn linkOneShot(self: *MachO, comp: *Compilation, prog_node: *std.Progress.Node)
         man.hash.addOptional(self.base.options.search_strategy);
         man.hash.addOptional(self.base.options.headerpad_size);
         man.hash.add(self.base.options.headerpad_max_install_names);
-        man.hash.add(dead_strip);
+        man.hash.add(gc_sections);
         man.hash.add(self.base.options.dead_strip_dylibs);
         man.hash.add(self.base.options.strip);
         man.hash.addListOfBytes(self.base.options.lib_dirs);
@@ -1068,7 +1069,7 @@ fn linkOneShot(self: *MachO, comp: *Compilation, prog_node: *std.Progress.Node)
                 try argv.append("-headerpad_max_install_names");
             }
 
-            if (dead_strip) {
+            if (gc_sections) {
                 try argv.append("-dead_strip");
             }
 
@@ -1186,19 +1187,12 @@ fn linkOneShot(self: *MachO, comp: *Compilation, prog_node: *std.Progress.Node)
 
         try self.createTentativeDefAtoms();
 
-        if (dead_strip) {
-            var gc_roots = std.AutoHashMap(*Atom, void).init(gpa);
-            defer gc_roots.deinit();
-
-            for (self.objects.items) |*object, object_id| {
-                try object.splitIntoAtomsOneShot(self, @intCast(u32, object_id), &gc_roots);
-            }
+        for (self.objects.items) |*object, object_id| {
+            try object.splitIntoAtomsOneShot(self, @intCast(u32, object_id));
+        }
 
-            try self.gcAtoms(&gc_roots);
-        } else {
-            for (self.objects.items) |*object, object_id| {
-                try object.splitIntoAtomsOneShot(self, @intCast(u32, object_id), null);
-            }
+        if (gc_sections) {
+            try dead_strip.gcAtoms(self);
         }
 
         try self.pruneAndSortSections();
@@ -5504,227 +5498,6 @@ fn pruneAndSortSections(self: *MachO) !void {
     self.sections_order_dirty = false;
 }
 
-fn gcAtoms(self: *MachO, gc_roots: *std.AutoHashMap(*Atom, void)) !void {
-    assert(self.base.options.gc_sections.?);
-
-    const gpa = self.base.allocator;
-
-    if (self.base.options.output_mode == .Exe) {
-        // Add entrypoint as GC root
-        const global = try self.getEntryPoint();
-        const atom = self.getAtomForSymbol(global).?; // panic here means fatal error
-        _ = try gc_roots.getOrPut(atom);
-    } else {
-        assert(self.base.options.output_mode == .Lib);
-        // Add exports as GC roots
-        for (self.globals.values()) |global| {
-            const sym = self.getSymbol(global);
-            if (!sym.sect()) continue;
-            const atom = self.getAtomForSymbol(global) orelse {
-                log.debug("skipping {s}", .{self.getSymbolName(global)});
-                continue;
-            };
-            _ = try gc_roots.getOrPut(atom);
-        }
-    }
-    // TODO just a temp until we learn how to parse unwind records
-    if (self.globals.get("___gxx_personality_v0")) |global| {
-        if (self.getAtomForSymbol(global)) |atom| {
-            _ = try gc_roots.getOrPut(atom);
-        }
-    }
-
-    var stack = std.ArrayList(*Atom).init(gpa);
-    defer stack.deinit();
-    try stack.ensureUnusedCapacity(gc_roots.count());
-
-    var alive = std.AutoHashMap(*Atom, void).init(gpa);
-    defer alive.deinit();
-    try alive.ensureUnusedCapacity(gc_roots.count());
-
-    log.debug("GC roots:", .{});
-    var gc_roots_it = gc_roots.keyIterator();
-    while (gc_roots_it.next()) |gc_root| {
-        self.logAtom(gc_root.*);
-        stack.appendAssumeCapacity(gc_root.*);
-        alive.putAssumeCapacity(gc_root.*, {});
-    }
-
-    while (stack.popOrNull()) |source_atom| {
-        for (source_atom.relocs.items) |rel| {
-            if (rel.getTargetAtom(self)) |target_atom| {
-                const gop = try alive.getOrPut(target_atom);
-                if (!gop.found_existing) {
-                    log.debug("  retained ATOM(%{d}, '{s}') in object({d})", .{
-                        target_atom.sym_index,
-                        target_atom.getName(self),
-                        target_atom.file,
-                    });
-                    log.debug("    referenced by ATOM(%{d}, '{s}') in object({d})", .{
-                        source_atom.sym_index,
-                        source_atom.getName(self),
-                        source_atom.file,
-                    });
-                    try stack.append(target_atom);
-                }
-            }
-        }
-    }
-    // TODO live support
-
-    // Any section that ends up here will be updated, that is,
-    // its size and alignment recalculated.
-    var gc_sections = std.AutoHashMap(MatchingSection, void).init(gpa);
-    defer gc_sections.deinit();
-
-    var loop: bool = true;
-    while (loop) {
-        loop = false;
-
-        for (self.objects.items) |object| {
-            for (object.getSourceSymtab()) |_, source_index| {
-                const atom = object.getAtomForSymbol(@intCast(u32, source_index)) orelse continue;
-                if (alive.contains(atom)) continue;
-
-                const global = atom.getSymbolWithLoc();
-                const sym = atom.getSymbolPtr(self);
-                const match = self.getMatchingSectionFromOrdinal(sym.n_sect);
-
-                if (sym.n_desc == N_DESC_GCED) continue;
-                if (!sym.ext()) {
-                    for (atom.relocs.items) |rel| {
-                        if (rel.getTargetAtom(self)) |target_atom| {
-                            const target_sym = target_atom.getSymbol(self);
-                            if (target_sym.n_desc == N_DESC_GCED) break;
-                        }
-                    } else continue;
-                }
-
-                self.logAtom(atom);
-                sym.n_desc = N_DESC_GCED;
-                self.removeAtomFromSection(atom, match);
-                _ = try gc_sections.put(match, {});
-
-                for (atom.contained.items) |sym_off| {
-                    const inner = self.getSymbolPtr(.{
-                        .sym_index = sym_off.sym_index,
-                        .file = atom.file,
-                    });
-                    inner.n_desc = N_DESC_GCED;
-                }
-
-                if (self.got_entries_table.contains(global)) {
-                    const got_atom = self.getGotAtomForSymbol(global).?;
-                    const got_sym = got_atom.getSymbolPtr(self);
-                    got_sym.n_desc = N_DESC_GCED;
-                }
-
-                if (self.stubs_table.contains(global)) {
-                    const stubs_atom = self.getStubsAtomForSymbol(global).?;
-                    const stubs_sym = stubs_atom.getSymbolPtr(self);
-                    stubs_sym.n_desc = N_DESC_GCED;
-                }
-
-                if (self.tlv_ptr_entries_table.contains(global)) {
-                    const tlv_ptr_atom = self.getTlvPtrAtomForSymbol(global).?;
-                    const tlv_ptr_sym = tlv_ptr_atom.getSymbolPtr(self);
-                    tlv_ptr_sym.n_desc = N_DESC_GCED;
-                }
-
-                loop = true;
-            }
-        }
-    }
-
-    for (self.got_entries.items) |entry| {
-        const sym = entry.getSymbol(self);
-        if (sym.n_desc != N_DESC_GCED) continue;
-
-        // TODO tombstone
-        const atom = entry.getAtom(self);
-        const match = self.getMatchingSectionFromOrdinal(sym.n_sect);
-        self.removeAtomFromSection(atom, match);
-        _ = try gc_sections.put(match, {});
-        _ = self.got_entries_table.remove(entry.target);
-    }
-
-    for (self.stubs.items) |entry| {
-        const sym = entry.getSymbol(self);
-        if (sym.n_desc != N_DESC_GCED) continue;
-
-        // TODO tombstone
-        const atom = entry.getAtom(self);
-        const match = self.getMatchingSectionFromOrdinal(sym.n_sect);
-        self.removeAtomFromSection(atom, match);
-        _ = try gc_sections.put(match, {});
-        _ = self.stubs_table.remove(entry.target);
-    }
-
-    for (self.tlv_ptr_entries.items) |entry| {
-        const sym = entry.getSymbol(self);
-        if (sym.n_desc != N_DESC_GCED) continue;
-
-        // TODO tombstone
-        const atom = entry.getAtom(self);
-        const match = self.getMatchingSectionFromOrdinal(sym.n_sect);
-        self.removeAtomFromSection(atom, match);
-        _ = try gc_sections.put(match, {});
-        _ = self.tlv_ptr_entries_table.remove(entry.target);
-    }
-
-    var gc_sections_it = gc_sections.iterator();
-    while (gc_sections_it.next()) |entry| {
-        const match = entry.key_ptr.*;
-        const sect = self.getSectionPtr(match);
-        if (sect.size == 0) continue; // Pruning happens automatically in next step.
-
-        sect.@"align" = 0;
-        sect.size = 0;
-
-        var atom = self.atoms.get(match).?;
-
-        while (atom.prev) |prev| {
-            atom = prev;
-        }
-
-        while (true) {
-            const atom_alignment = try math.powi(u32, 2, atom.alignment);
-            const aligned_end_addr = mem.alignForwardGeneric(u64, sect.size, atom_alignment);
-            const padding = aligned_end_addr - sect.size;
-            sect.size += padding + atom.size;
-            sect.@"align" = @maximum(sect.@"align", atom.alignment);
-
-            if (atom.next) |next| {
-                atom = next;
-            } else break;
-        }
-    }
-}
-
-fn removeAtomFromSection(self: *MachO, atom: *Atom, match: MatchingSection) void {
-    const sect = self.getSectionPtr(match);
-
-    // If we want to enable GC for incremental codepath, we need to take into
-    // account any padding that might have been left here.
-    sect.size -= atom.size;
-
-    if (atom.prev) |prev| {
-        prev.next = atom.next;
-    }
-    if (atom.next) |next| {
-        next.prev = atom.prev;
-    } else {
-        const last = self.atoms.getPtr(match).?;
-        if (atom.prev) |prev| {
-            last.* = prev;
-        } else {
-            // The section will be GCed in the next step.
-            last.* = undefined;
-            sect.size = 0;
-        }
-    }
-}
-
 fn updateSectionOrdinals(self: *MachO) !void {
     if (!self.sections_order_dirty) return;
 
@@ -6217,20 +5990,18 @@ fn writeDataInCode(self: *MachO) !void {
 
     for (self.objects.items) |object| {
         const dice = object.parseDataInCode() orelse continue;
-        const source_symtab = object.getSourceSymtab();
         try out_dice.ensureUnusedCapacity(dice.len);
 
         for (object.managed_atoms.items) |atom| {
             const sym = atom.getSymbol(self);
             if (sym.n_desc == N_DESC_GCED) continue;
-            if (atom.sym_index >= source_symtab.len) continue; // synthetic, linker generated
 
             const match = self.getMatchingSectionFromOrdinal(sym.n_sect);
             if (match.seg != self.text_segment_cmd_index.? and match.sect != self.text_section_index.?) {
                 continue;
             }
 
-            const source_sym = source_symtab[atom.sym_index];
+            const source_sym = object.getSourceSymbol(atom.sym_index) orelse continue;
             const source_addr = math.cast(u32, source_sym.n_value) orelse return error.Overflow;
             const filtered_dice = filterDataInCode(dice, source_addr, source_addr + atom.size);
             const base = math.cast(u32, sym.n_value - text_sect.addr + text_sect.offset) orelse
@@ -6886,16 +6657,14 @@ fn generateSymbolStabsForSymbol(
 ) ![]const macho.nlist_64 {
     const gpa = self.base.allocator;
     const object = self.objects.items[sym_loc.file.?];
-    const source_symtab = object.getSourceSymtab();
     const sym = self.getSymbol(sym_loc);
     const sym_name = self.getSymbolName(sym_loc);
 
     if (sym.n_strx == 0) return buf[0..0];
     if (sym.n_desc == N_DESC_GCED) return buf[0..0];
     if (self.symbolIsTemp(sym_loc)) return buf[0..0];
-    if (sym_loc.sym_index >= source_symtab.len) return buf[0..0]; // synthetic, linker generated
 
-    const source_sym = source_symtab[sym_loc.sym_index];
+    const source_sym = object.getSourceSymbol(sym_loc.sym_index) orelse return buf[0..0];
     const size: ?u64 = size: {
         if (source_sym.tentative()) break :size null;
         for (debug_info.inner.func_list.items) |func| {
@@ -7353,7 +7122,7 @@ fn logAtoms(self: *MachO) void {
     }
 }
 
-fn logAtom(self: *MachO, atom: *const Atom) void {
+pub fn logAtom(self: *MachO, atom: *const Atom) void {
     const sym = atom.getSymbol(self);
     const sym_name = atom.getName(self);
     log.debug("  ATOM(%{d}, '{s}') @ {x} (sizeof({x}), alignof({x})) in object({d}) in sect({d})", .{
diff --git a/src/link/MachO/Atom.zig b/src/link/MachO/Atom.zig
index acaeab7a88..2f60702423 100644
--- a/src/link/MachO/Atom.zig
+++ b/src/link/MachO/Atom.zig
@@ -308,7 +308,7 @@ pub fn parseRelocs(self: *Atom, relocs: []const macho.relocation_info, context:
             if (rel.r_extern == 0) {
                 const sect_id = @intCast(u16, rel.r_symbolnum - 1);
                 const sym_index = object.sections_as_symbols.get(sect_id) orelse blk: {
-                    const sect = object.getSection(sect_id);
+                    const sect = object.getSourceSection(sect_id);
                     const match = (try context.macho_file.getMatchingSection(sect)) orelse
                         unreachable;
                     const sym_index = @intCast(u32, object.symtab.items.len);
@@ -360,7 +360,7 @@ pub fn parseRelocs(self: *Atom, relocs: []const macho.relocation_info, context:
                         else
                             mem.readIntLittle(i32, self.code.items[offset..][0..4]);
                         if (rel.r_extern == 0) {
-                            const target_sect_base_addr = object.getSection(@intCast(u16, rel.r_symbolnum - 1)).addr;
+                            const target_sect_base_addr = object.getSourceSection(@intCast(u16, rel.r_symbolnum - 1)).addr;
                             addend -= @intCast(i64, target_sect_base_addr);
                         }
                         try self.addPtrBindingOrRebase(rel, target, context);
@@ -392,7 +392,7 @@ pub fn parseRelocs(self: *Atom, relocs: []const macho.relocation_info, context:
                         else
                             mem.readIntLittle(i32, self.code.items[offset..][0..4]);
                         if (rel.r_extern == 0) {
-                            const target_sect_base_addr = object.getSection(@intCast(u16, rel.r_symbolnum - 1)).addr;
+                            const target_sect_base_addr = object.getSourceSection(@intCast(u16, rel.r_symbolnum - 1)).addr;
                             addend -= @intCast(i64, target_sect_base_addr);
                         }
                         try self.addPtrBindingOrRebase(rel, target, context);
@@ -413,7 +413,7 @@ pub fn parseRelocs(self: *Atom, relocs: []const macho.relocation_info, context:
                         if (rel.r_extern == 0) {
                             // Note for the future self: when r_extern == 0, we should subtract correction from the
                             // addend.
-                            const target_sect_base_addr = object.getSection(@intCast(u16, rel.r_symbolnum - 1)).addr;
+                            const target_sect_base_addr = object.getSourceSection(@intCast(u16, rel.r_symbolnum - 1)).addr;
                             // We need to add base_offset, i.e., offset of this atom wrt to the source
                             // section. Otherwise, the addend will over-/under-shoot.
                             addend += @intCast(i64, context.base_addr + offset + 4) -
diff --git a/src/link/MachO/Object.zig b/src/link/MachO/Object.zig
index f6b50cd0ae..5e10c0c0a3 100644
--- a/src/link/MachO/Object.zig
+++ b/src/link/MachO/Object.zig
@@ -285,12 +285,7 @@ fn filterRelocs(
 }
 
 /// Splits object into atoms assuming one-shot linking mode.
-pub fn splitIntoAtomsOneShot(
-    self: *Object,
-    macho_file: *MachO,
-    object_id: u32,
-    gc_roots: ?*std.AutoHashMap(*Atom, void),
-) !void {
+pub fn splitIntoAtomsOneShot(self: *Object, macho_file: *MachO, object_id: u32) !void {
     assert(macho_file.mode == .one_shot);
 
     const tracy = trace(@src());
@@ -338,10 +333,7 @@ pub fn splitIntoAtomsOneShot(
 
     // We only care about defined symbols, so filter every other out.
     const sorted_syms = sorted_all_syms.items[0..iundefsym];
-    const dead_strip = macho_file.base.options.gc_sections orelse false;
-    const subsections_via_symbols = self.header.flags & macho.MH_SUBSECTIONS_VIA_SYMBOLS != 0 and
-        (macho_file.base.options.optimize_mode != .Debug or dead_strip);
-    // const subsections_via_symbols = self.header.flags & macho.MH_SUBSECTIONS_VIA_SYMBOLS != 0;
+    const subsections_via_symbols = self.header.flags & macho.MH_SUBSECTIONS_VIA_SYMBOLS != 0;
 
     for (seg.sections.items) |sect, id| {
         const sect_id = @intCast(u8, id);
@@ -417,7 +409,6 @@ pub fn splitIntoAtomsOneShot(
                     &.{},
                     match,
                     sect,
-                    gc_roots,
                 );
                 try macho_file.addAtomToSection(atom, match);
             }
@@ -473,7 +464,6 @@ pub fn splitIntoAtomsOneShot(
                     sorted_atom_syms.items[1..],
                     match,
                     sect,
-                    gc_roots,
                 );
 
                 if (arch == .x86_64 and addr == sect.addr) {
@@ -528,7 +518,6 @@ pub fn splitIntoAtomsOneShot(
                 filtered_syms,
                 match,
                 sect,
-                gc_roots,
             );
             try macho_file.addAtomToSection(atom, match);
         }
@@ -547,7 +536,6 @@ fn createAtomFromSubsection(
     indexes: []const SymbolAtIndex,
     match: MatchingSection,
     sect: macho.section_64,
-    gc_roots: ?*std.AutoHashMap(*Atom, void),
 ) !*Atom {
     const gpa = macho_file.base.allocator;
     const sym = self.symtab.items[sym_index];
@@ -597,21 +585,6 @@ fn createAtomFromSubsection(
         try self.atom_by_index_table.putNoClobber(gpa, inner_sym_index.index, atom);
     }
 
-    if (gc_roots) |gcr| {
-        const is_gc_root = blk: {
-            if (sect.isDontDeadStrip()) break :blk true;
-            switch (sect.type_()) {
-                macho.S_MOD_INIT_FUNC_POINTERS,
-                macho.S_MOD_TERM_FUNC_POINTERS,
-                => break :blk true,
-                else => break :blk false,
-            }
-        };
-        if (is_gc_root) {
-            try gcr.putNoClobber(atom, {});
-        }
-    }
-
     return atom;
 }
 
@@ -633,6 +606,18 @@ pub fn getSourceSymtab(self: Object) []const macho.nlist_64 {
     );
 }
 
+pub fn getSourceSymbol(self: Object, index: u32) ?macho.nlist_64 {
+    const symtab = self.getSourceSymtab();
+    if (index >= symtab.len) return null;
+    return symtab[index];
+}
+
+pub fn getSourceSection(self: Object, index: u16) macho.section_64 {
+    const seg = self.load_commands.items[self.segment_cmd_index.?].segment;
+    assert(index < seg.sections.items.len);
+    return seg.sections.items[index];
+}
+
 pub fn parseDataInCode(self: Object) ?[]const macho.data_in_code_entry {
     const index = self.data_in_code_cmd_index orelse return null;
     const data_in_code = self.load_commands.items[index].linkedit_data;
@@ -643,8 +628,8 @@ pub fn parseDataInCode(self: Object) ?[]const macho.data_in_code_entry {
     );
 }
 
-pub fn getSectionContents(self: Object, sect_id: u16) error{Overflow}![]const u8 {
-    const sect = self.getSection(sect_id);
+pub fn getSectionContents(self: Object, index: u16) error{Overflow}![]const u8 {
+    const sect = self.getSourceSection(index);
     const size = math.cast(usize, sect.size) orelse return error.Overflow;
     log.debug("getting {s},{s} data at 0x{x} - 0x{x}", .{
         sect.segName(),
@@ -660,12 +645,6 @@ pub fn getString(self: Object, off: u32) []const u8 {
     return mem.sliceTo(@ptrCast([*:0]const u8, self.strtab.ptr + off), 0);
 }
 
-pub fn getSection(self: Object, n_sect: u16) macho.section_64 {
-    const seg = self.load_commands.items[self.segment_cmd_index.?].segment;
-    assert(n_sect < seg.sections.items.len);
-    return seg.sections.items[n_sect];
-}
-
 pub fn getAtomForSymbol(self: Object, sym_index: u32) ?*Atom {
     return self.atom_by_index_table.get(sym_index);
 }
diff --git a/src/link/MachO/dead_strip.zig b/src/link/MachO/dead_strip.zig
new file mode 100644
index 0000000000..a953e5bc19
--- /dev/null
+++ b/src/link/MachO/dead_strip.zig
@@ -0,0 +1,293 @@
+const std = @import("std");
+const assert = std.debug.assert;
+const log = std.log.scoped(.dead_strip);
+const macho = std.macho;
+const math = std.math;
+const mem = std.mem;
+
+const Allocator = mem.Allocator;
+const Atom = @import("Atom.zig");
+const MachO = @import("../MachO.zig");
+const MatchingSection = MachO.MatchingSection;
+
+pub fn gcAtoms(macho_file: *MachO) !void {
+    assert(macho_file.base.options.gc_sections.?);
+
+    const gpa = macho_file.base.allocator;
+    var arena_allocator = std.heap.ArenaAllocator.init(gpa);
+    defer arena_allocator.deinit();
+    const arena = arena_allocator.allocator();
+
+    var roots = std.AutoHashMap(*Atom, void).init(arena);
+    try collectRoots(&roots, macho_file);
+
+    var alive = std.AutoHashMap(*Atom, void).init(arena);
+    try mark(roots, &alive, macho_file);
+
+    try prune(arena, alive, macho_file);
+}
+
+fn removeAtomFromSection(atom: *Atom, match: MatchingSection, macho_file: *MachO) void {
+    const sect = macho_file.getSectionPtr(match);
+
+    // If we want to enable GC for incremental codepath, we need to take into
+    // account any padding that might have been left here.
+    sect.size -= atom.size;
+
+    if (atom.prev) |prev| {
+        prev.next = atom.next;
+    }
+    if (atom.next) |next| {
+        next.prev = atom.prev;
+    } else {
+        const last = macho_file.atoms.getPtr(match).?;
+        if (atom.prev) |prev| {
+            last.* = prev;
+        } else {
+            // The section will be GCed in the next step.
+            last.* = undefined;
+            sect.size = 0;
+        }
+    }
+}
+
+fn collectRoots(roots: *std.AutoHashMap(*Atom, void), macho_file: *MachO) !void {
+    const output_mode = macho_file.base.options.output_mode;
+
+    switch (output_mode) {
+        .Exe => {
+            // Add entrypoint as GC root
+            const global = try macho_file.getEntryPoint();
+            const atom = macho_file.getAtomForSymbol(global).?; // panic here means fatal error
+            _ = try roots.getOrPut(atom);
+        },
+        else => |other| {
+            assert(other == .Lib);
+            // Add exports as GC roots
+            for (macho_file.globals.values()) |global| {
+                const sym = macho_file.getSymbol(global);
+                if (!sym.sect()) continue;
+                const atom = macho_file.getAtomForSymbol(global) orelse {
+                    log.debug("skipping {s}", .{macho_file.getSymbolName(global)});
+                    continue;
+                };
+                _ = try roots.getOrPut(atom);
+                log.debug("adding root", .{});
+                macho_file.logAtom(atom);
+            }
+        },
+    }
+
+    // TODO just a temp until we learn how to parse unwind records
+    if (macho_file.globals.get("___gxx_personality_v0")) |global| {
+        if (macho_file.getAtomForSymbol(global)) |atom| {
+            _ = try roots.getOrPut(atom);
+            log.debug("adding root", .{});
+            macho_file.logAtom(atom);
+        }
+    }
+
+    for (macho_file.objects.items) |object| {
+        for (object.managed_atoms.items) |atom| {
+            const source_sym = object.getSourceSymbol(atom.sym_index) orelse continue;
+            if (source_sym.tentative()) continue;
+            const source_sect = object.getSourceSection(source_sym.n_sect - 1);
+            const is_gc_root = blk: {
+                if (source_sect.isDontDeadStrip()) break :blk true;
+                switch (source_sect.type_()) {
+                    macho.S_MOD_INIT_FUNC_POINTERS,
+                    macho.S_MOD_TERM_FUNC_POINTERS,
+                    => break :blk true,
+                    else => break :blk false,
+                }
+            };
+            if (is_gc_root) {
+                try roots.putNoClobber(atom, {});
+                log.debug("adding root", .{});
+                macho_file.logAtom(atom);
+            }
+        }
+    }
+}
+
+fn markLive(atom: *Atom, alive: *std.AutoHashMap(*Atom, void), macho_file: *MachO) anyerror!void {
+    const gop = try alive.getOrPut(atom);
+    if (gop.found_existing) return;
+
+    log.debug("marking live", .{});
+    macho_file.logAtom(atom);
+
+    for (atom.relocs.items) |rel| {
+        const target_atom = rel.getTargetAtom(macho_file) orelse continue;
+        try markLive(target_atom, alive, macho_file);
+    }
+}
+
+fn refersLive(atom: *Atom, alive: std.AutoHashMap(*Atom, void), macho_file: *MachO) bool {
+    for (atom.relocs.items) |rel| {
+        const target_atom = rel.getTargetAtom(macho_file) orelse continue;
+        if (alive.contains(target_atom)) return true;
+    }
+    return false;
+}
+
+fn refersDead(atom: *Atom, macho_file: *MachO) bool {
+    for (atom.relocs.items) |rel| {
+        const target_atom = rel.getTargetAtom(macho_file) orelse continue;
+        const target_sym = target_atom.getSymbol(macho_file);
+        if (target_sym.n_desc == MachO.N_DESC_GCED) return true;
+    }
+    return false;
+}
+
+fn mark(
+    roots: std.AutoHashMap(*Atom, void),
+    alive: *std.AutoHashMap(*Atom, void),
+    macho_file: *MachO,
+) !void {
+    try alive.ensureUnusedCapacity(roots.count());
+
+    var it = roots.keyIterator();
+    while (it.next()) |root| {
+        try markLive(root.*, alive, macho_file);
+    }
+
+    var loop: bool = true;
+    while (loop) {
+        loop = false;
+
+        for (macho_file.objects.items) |object| {
+            for (object.managed_atoms.items) |atom| {
+                if (alive.contains(atom)) continue;
+                const source_sym = object.getSourceSymbol(atom.sym_index) orelse continue;
+                if (source_sym.tentative()) continue;
+                const source_sect = object.getSourceSection(source_sym.n_sect - 1);
+                if (source_sect.isDontDeadStripIfReferencesLive() and refersLive(atom, alive.*, macho_file)) {
+                    try markLive(atom, alive, macho_file);
+                    loop = true;
+                }
+            }
+        }
+    }
+}
+
+fn prune(arena: Allocator, alive: std.AutoHashMap(*Atom, void), macho_file: *MachO) !void {
+    // Any section that ends up here will be updated, that is,
+    // its size and alignment recalculated.
+    var gc_sections = std.AutoHashMap(MatchingSection, void).init(arena);
+    var loop: bool = true;
+    while (loop) {
+        loop = false;
+
+        for (macho_file.objects.items) |object| {
+            for (object.getSourceSymtab()) |_, source_index| {
+                const atom = object.getAtomForSymbol(@intCast(u32, source_index)) orelse continue;
+                if (alive.contains(atom)) continue;
+
+                const global = atom.getSymbolWithLoc();
+                const sym = atom.getSymbolPtr(macho_file);
+                const match = macho_file.getMatchingSectionFromOrdinal(sym.n_sect);
+
+                if (sym.n_desc == MachO.N_DESC_GCED) continue;
+                if (!sym.ext() and !refersDead(atom, macho_file)) continue;
+
+                macho_file.logAtom(atom);
+                sym.n_desc = MachO.N_DESC_GCED;
+                removeAtomFromSection(atom, match, macho_file);
+                _ = try gc_sections.put(match, {});
+
+                for (atom.contained.items) |sym_off| {
+                    const inner = macho_file.getSymbolPtr(.{
+                        .sym_index = sym_off.sym_index,
+                        .file = atom.file,
+                    });
+                    inner.n_desc = MachO.N_DESC_GCED;
+                }
+
+                if (macho_file.got_entries_table.contains(global)) {
+                    const got_atom = macho_file.getGotAtomForSymbol(global).?;
+                    const got_sym = got_atom.getSymbolPtr(macho_file);
+                    got_sym.n_desc = MachO.N_DESC_GCED;
+                }
+
+                if (macho_file.stubs_table.contains(global)) {
+                    const stubs_atom = macho_file.getStubsAtomForSymbol(global).?;
+                    const stubs_sym = stubs_atom.getSymbolPtr(macho_file);
+                    stubs_sym.n_desc = MachO.N_DESC_GCED;
+                }
+
+                if (macho_file.tlv_ptr_entries_table.contains(global)) {
+                    const tlv_ptr_atom = macho_file.getTlvPtrAtomForSymbol(global).?;
+                    const tlv_ptr_sym = tlv_ptr_atom.getSymbolPtr(macho_file);
+                    tlv_ptr_sym.n_desc = MachO.N_DESC_GCED;
+                }
+
+                loop = true;
+            }
+        }
+    }
+
+    for (macho_file.got_entries.items) |entry| {
+        const sym = entry.getSymbol(macho_file);
+        if (sym.n_desc != MachO.N_DESC_GCED) continue;
+
+        // TODO tombstone
+        const atom = entry.getAtom(macho_file);
+        const match = macho_file.getMatchingSectionFromOrdinal(sym.n_sect);
+        removeAtomFromSection(atom, match, macho_file);
+        _ = try gc_sections.put(match, {});
+        _ = macho_file.got_entries_table.remove(entry.target);
+    }
+
+    for (macho_file.stubs.items) |entry| {
+        const sym = entry.getSymbol(macho_file);
+        if (sym.n_desc != MachO.N_DESC_GCED) continue;
+
+        // TODO tombstone
+        const atom = entry.getAtom(macho_file);
+        const match = macho_file.getMatchingSectionFromOrdinal(sym.n_sect);
+        removeAtomFromSection(atom, match, macho_file);
+        _ = try gc_sections.put(match, {});
+        _ = macho_file.stubs_table.remove(entry.target);
+    }
+
+    for (macho_file.tlv_ptr_entries.items) |entry| {
+        const sym = entry.getSymbol(macho_file);
+        if (sym.n_desc != MachO.N_DESC_GCED) continue;
+
+        // TODO tombstone
+        const atom = entry.getAtom(macho_file);
+        const match = macho_file.getMatchingSectionFromOrdinal(sym.n_sect);
+        removeAtomFromSection(atom, match, macho_file);
+        _ = try gc_sections.put(match, {});
+        _ = macho_file.tlv_ptr_entries_table.remove(entry.target);
+    }
+
+    var gc_sections_it = gc_sections.iterator();
+    while (gc_sections_it.next()) |entry| {
+        const match = entry.key_ptr.*;
+        const sect = macho_file.getSectionPtr(match);
+        if (sect.size == 0) continue; // Pruning happens automatically in next step.
+
+        sect.@"align" = 0;
+        sect.size = 0;
+
+        var atom = macho_file.atoms.get(match).?;
+
+        while (atom.prev) |prev| {
+            atom = prev;
+        }
+
+        while (true) {
+            const atom_alignment = try math.powi(u32, 2, atom.alignment);
+            const aligned_end_addr = mem.alignForwardGeneric(u64, sect.size, atom_alignment);
+            const padding = aligned_end_addr - sect.size;
+            sect.size += padding + atom.size;
+            sect.@"align" = @maximum(sect.@"align", atom.alignment);
+
+            if (atom.next) |next| {
+                atom = next;
+            } else break;
+        }
+    }
+}