cdc31cfa66f0 made every root that references an already-marked subtree
re-walk that subtree to record the completeness dependencies it
contributes, which is what makes the recorded dependency set complete
and independent of thread interleaving. That walk replaced the
isAlreadyMarked short-circuit which had kept marking linear, so a widely
shared subtree is re-parsed and re-resolved once per referencing root.
Linking a RelWithDebInfo clang went from 27s to 67s of wall time and
from 242s to 1447s of CPU, peak memory grew from 35GB to 63GB, and 7.0
billion dependencies were recorded for an unchanged dSYM.
Record only that a root carries the subtree's dependencies and walk each
distinct subtree once. All of a subtree's dependencies demote the same
root, so the expansion stops at the first one that does.
A subtree contributes two kinds of dependency. One kind is recorded
under the root referencing the subtree, varies with that root, and is
summarized so it can be applied to each referencing root in turn. The
other is recorded under a subprogram nested inside the subtree, names
that subprogram, and is therefore the same for every referencing root,
so recording it once is enough. Which kind applies is carried explicitly
through the walk. Only a subprogram re-anchors the root, so a subtree
that is itself a subprogram is already anchored to itself, and
recovering the split by comparing root entries would make it depend on
which reference of the subtree happens to be walked first.
The walk has to happen when completeness is checked rather than during
marking. Marking consults the keep and placement bits through
isAlreadyMarked while sibling units are still raising them, so a subtree
walked then yields a result that depends on how the units interleave and
cannot stand in for the rest. A walk that only records dependencies
never consults those bits. It reads a DIE's ODR availability and whether
it has an address, both of which settle before marking begins.
Every DWARF section stays byte identical to cdc31cfa66f0 for dsymutil
runs over llvm-cxxfilt, llvm-dwarfdump and llvm-mc, single threaded and
across repeated runs at eight threads. Ordering inside __debug_names
still varies between runs, as it does before this change.
Assisted-by: Claude
(cherry picked from commit b704e514dca4860cb436b0c47f1748255a0f82af)
Jonas Devlieghere
cefac32eb6