dsymutil links the DWARF from a program’s object files into a .dSYM bundle. The part that does the actual work is the DWARF linker. LLVM provides two implementations: the original classic linker and the parallel linker, a modern rewrite that became the default in June after it was deemed ready for widespread adoption. The classic linker remains available through --linker=classic.

Both take the same input and should produce equivalent debug info. The classic linker does most of its work on one thread in a fixed order, while the parallel linker distributes the work across all available cores. The parallel linker must make its output independent of the order in which threads complete their work. I’ve written about the classic linker’s lockstep algorithm before. This post puts the two side by side.

What a DWARF Linker Does

On Darwin, the static linker doesn’t copy DWARF into the executable. It leaves the debug info in the object files and records a debug map that identifies which object files contributed to the binary and, for each of them, which symbols were kept and at what address. The DWARF linker reads the object files and the debug map and writes one set of DWARF sections for the whole program.

Consider the example below: two source files that share a header.

// geo.h
namespace geo {
struct Point { int x, y; };
inline int twice(const Point &p) { return 2 * (p.x + p.y); }
}

// a.cpp
#include "geo.h"
int use_b(const geo::Point &p);
int main() { geo::Point p{1, 2}; return geo::twice(p) + use_b(p); }

// b.cpp
#include "geo.h"
int use_b(const geo::Point &p) { return geo::twice(p); }

Both object files describe geo::Point, and both contain a copy of geo::twice. The static linker kept the copy from a.o, so the debug map only lists twice under a.o.

The figures in this post show what the two linkers generate for this example. Debug info entries (DIEs) from a.o are blue, those from b.o are orange, and linker-generated entries are green.

The DWARF linker reads a.o, b.o and the debug map of prog, and writes prog.dSYM

The DWARF linker has four responsibilities:

  1. Relocate addresses. Object files contain relative addresses, while the debug map provides their relocated addresses.
  2. Drop the DIEs for code that the static linker dropped. In the example that’s the copy of twice in b.o.
  3. Emit only one copy of a type when several units describe it by taking advantage of the C++ One Definition Rule (ODR). geo::Point is such a type.
  4. Assign final values to string offsets, abbreviation codes, cross-unit references, and range and location list offsets.

How the linkers assign these values accounts for much of the difference between their designs. A reference from one unit to a DIE in another, a DW_FORM_ref_addr, is an offset from the start of .debug_info. It depends on the size of everything written before its target. The classic linker assigns offsets while it clones DIEs, so it has to clone them in one fixed order. The parallel linker clones each unit into per-unit buffers and assigns offsets afterwards, so it can clone units in any order and on any thread.

Scheduling

The classic linker processes object files one at a time, in debug map order, on two threads that move in lockstep. The first thread runs the analysis phase. It parses the DIEs of an object file, records the parent of each one, and works out which DeclContext each DIE belongs to—information later used for ODR uniquing. The second thread runs the cloning phase, which only starts on an object file once its analysis is complete. It decides which DIEs are live, clones them, and streams them to the output together with the unit’s line table, ranges and location lists. In the meantime, the first thread analyzes the next object file.

The two threads of the classic linker: an object file is cloned after its analysis, while the next one is analyzed

The cloning thread also assigns DIE offsets, string offsets and abbreviation codes as it writes the output. All units share one string table and one abbreviation table. Processing this shared state on a single thread makes the output deterministic, but also creates a bottleneck that prevents the classic linker from making use of more than two threads. Once an object file is written, its DIEs are freed, so only one object file’s cloned DIEs are in memory at a time.

The parallel linker schedules work at the compile-unit level. The thread pool processes object files, scheduling each compile unit within them as a separate task. A unit loads its DIEs, marks what’s live, names its types, clones the live DIEs into buffers that belong to the unit, and frees its input. Unlike the classic linker’s lockstep pipeline, compile units ordinarily proceed through these stages independently.

Units that reference each other are the exception. In the input, a DW_FORM_ref_addr can point into another unit of the same object file, which is possible with Link Time Optimization (LTO). Because liveness in one unit then depends on the other, such units stop after loading and advance together, one stage at a time. Their liveness stage repeats until it finds no new references between units.

The tasks share two concurrent hash tables, one for strings and one for types. After processing all object files, the linker uses the type table to build an ordinary compile unit containing the types shared between units. The linker calls this the type unit, although it isn’t a DWARF type unit (DW_UT_type) and has no type signature. It then assigns each buffer a location in the output, patches the values that depend on the final layout, and writes the sections.

The stages of the parallel linker: units with no references to other units run them back to back, and units that reference each other advance together

Liveness and the Parent Walk

Both linkers use the debug map to seed liveness. If it provides an address for a DIE, the corresponding code or data was kept by the static linker and the DIE becomes a root. This covers functions, labels and variables with static storage, while base types are always kept. From a kept DIE, three kinds of related DIEs are kept as well:

  • the DIEs it references, such as its type
  • its children when they are necessary for completeness, such as the members of a struct
  • its ancestors, since a function in a namespace needs the namespace DIE around it

Let’s take a look at b.o on its own, where use_b is the only root. Its parameter type leads through const Point & and const Point to geo::Point, which causes the struct’s members and its parent geo to be retained. The copy of twice has no address in the debug map and is dropped, even though its parent is kept.

The DIE tree of b.o, with the DIEs that are kept and the two that are dropped

The step from a kept DIE up to its ancestors is the parent walk. It keeps the ancestors but not their other children, unless an ancestor is itself incomplete without them.

The classic linker walks each unit once and marks DIEs with a keep bit. When it keeps a DIE, it walks up the parent chain and keeps each ancestor until it reaches one that’s already kept. References can lead into other units of the same object file, so the walk needs the parent links of every unit in that file. That’s why the analysis phase finishes a whole object file before the cloning phase starts on it.

The classic walk also considers ODR state. When a reference leads to a type whose definition an earlier object file already supplied, the walk stops there and the local copy is never marked. This happens in b.o: by the time it’s processed, a.o has supplied geo::Point, so neither Point nor geo is kept for b.o. Liveness in one object file therefore depends on the object files that precede it.

The parallel linker processes object files independently, so its liveness decisions depend only on the object file being processed. For each DIE, it decides whether to keep it and where to emit it: in its own unit, in the type unit, or in both.

With two destinations, there are two parent walks. A type assigned to the type unit needs its enclosing namespaces there, and a function that remains in its unit needs them in that unit. Each walk sets its own flag on the ancestors and, like the classic one, stops at the first ancestor that already has it. In the example, geo is emitted in both places: as the parent of Point in the type unit and as the parent of twice in the unit of a.cpp.

The marks of a DIE are bits in one atomic word. Most of the time only one thread works on a unit, but units that reference each other mark DIEs in each other’s trees at the same time.

Moving shared types into a separate compile unit introduces one constraint: a DIE in the type unit may only reference other DIEs in the type unit. If a type refers to something that has to stay in its own unit, such as a type from an anonymous namespace, the type is moved back to its unit as well. The linker repeats this check until it reaches a fixed point where no more types need to be moved.

ODR Uniquing

The linker receives two descriptions of geo::Point, but the ODR guarantees that both represent the same type, so one copy is enough. Both linkers perform ODR uniquing only for C++ and Objective-C++ units, because C has no such rule. For large C++ projects, ODR uniquing can make the difference between fitting within Mach-O’s 4GB limit or not.

The classic linker identifies a type by its DeclContext: the names of the enclosing scopes plus its own name, with the declaration file, line and byte size as a safeguard. Only DIEs that declare something by name are assigned one: namespaces, structs, classes, unions, enumerations, typedefs, members and functions. Pointer types, const types and base types are not assigned a DeclContext and are never shared.

The classic linker retains the first copy it encounters. When it clones the first live definition for a DeclContext, that DIE becomes the canonical DIE and its output offset is recorded in the context. From then on, a reference to the type becomes a DW_FORM_ref_addr to the recorded offset, and the local copy isn’t kept, as described above. The type stays in the unit that first defined it; “first” is well defined because one thread clones the object files in order.1

Classic output: const Point in the unit of b.cpp refers to struct Point in the unit of a.cpp

The unit of b.cpp keeps its own int, const Point & and const Point, with only the last of these pointing into the unit of a.cpp.

The parallel linker clones units concurrently, so it cannot use the first copy it encounters as the canonical definition.

A type is identified by a key computed from the DIE itself: its tag, the key of its enclosing scope, and its name. Functions, templates and arrays add the keys of their parameters, template arguments and dimensions. Unnamed types use their declaration position and their contents. Every type gets a key, including base types, pointers and const types. A key only depends on the unit’s own DIEs, so each unit computes its keys without coordination. Equal keys from different units map to the same entry in the shared type table.

The linker selects a definition based on link order. Every unit has a priority based on its position in the link order: the earlier it appears in the input, the higher its priority. When several units provide a definition for the same key, the definition from the highest-priority unit is selected. If a lower-priority unit clones its definition provisionally, a higher-priority unit can replace it later. The same definition is selected on every run, regardless of timing.

The selected definitions are moved from their original units into the type unit, which appears first in the output as a compile unit named __artificial_type_unit. The linker builds it after processing all object files by sorting the entries of the type table, ensuring that its layout does not depend on insertion order. The other units refer into it with DW_FORM_ref_addr.

Parallel output: the units of a.cpp and b.cpp refer into the artificial type unit

Every type in the type unit came from a.o, because a.o appears first in the link order. The units of a.cpp and b.cpp are left with their functions and an int each, since base types are always kept.

Writing the Output

The classic linker knows a DIE’s output offset as soon as it clones it, because everything before it is already laid out. A string is assigned its final offset the first time it’s seen. All units share one abbreviation table and, in DWARF 5, one string offsets table. References to DIEs that appear later in the same object file are fixed up before that file’s units are written.

In the parallel linker, each unit writes its sections into per-unit buffers. Wherever a value depends on the final layout, the unit writes a placeholder and records a patch. These patches cover string offsets, references into other units and into the type unit, and the offsets of range and location lists.

After all units are cloned, the linker assigns each buffer a start offset in a fixed order: the type unit first, then the units in debug map order. Strings receive their offsets in the same order, after which the patches are applied and the buffers are concatenated into the output sections.

Because units are written independently, each has its own abbreviation table and, in DWARF 5, its own string offsets table. The type unit is a special case: every thread adds to it, so indices into a string offsets table would depend on timing. It therefore refers to strings by their offset in .debug_str, using DW_FORM_strp, and fills in that offset using the same patching mechanism.

Trade-offs

The classic linker is deterministic by construction: one thread assigns DIE offsets, string offsets and abbreviation codes in a fixed order and holds the cloned DIEs of only one object file at a time. This thread is also the bottleneck, so additional cores don’t help.

For clang, using every core reduces the link time from roughly 3 minutes to about 40 seconds. This speedup comes at the cost of keeping the output of all units in memory until the final pass, maintaining separate tables per unit, and replacing the classic linker’s implicit reliance on order with explicit rules: a priority to select the retained type, a sort to lay out the type unit, and a fixed order to assign offsets.


  1. This is also why the per-object numbers printed by --statistics depend on the order in which the object files are processed. ↩︎