[lld-macho] Deduplicate fixed-width literals

Authored by int3 on Jun 11 2021, 4:49 PM.


[lld-macho] Deduplicate fixed-width literals

Conceptually, the implementation is pretty straightforward: we put each
literal value into a hashtable, and then write out the keys of that
hashtable at the end.

In contrast with ELF, the Mach-O format does not support variable-length
literals that aren't strings. Its literals are either 4, 8, or 16 bytes
in length. LLD-ELF dedups its literals via sorting + uniq'ing, but since
we don't need to worry about overly-long values, we should be able to do
a faster job by just hashing.

That said, the implementation right now is far from optimal, because we
add to those hashtables serially. To parallelize this, we'll need a
basic concurrent hashtable (only needs to support concurrent writes w/o
interleave reads), which shouldn't be to hard to implement, but I'd like
to punt on it for now.

Numbers for linking chromium_framework on my 3.2 GHz 16-Core Intel Xeon W:

    N           Min           Max        Median           Avg        Stddev
x  20          4.27          4.39         4.315        4.3225   0.033225703
+  20          4.36          4.82          4.44        4.4845    0.13152846
Difference at 95.0% confidence
        0.162 +/- 0.0613971
        3.74783% +/- 1.42041%
        (Student's t, pooled s = 0.0959262)

This corresponds to binary size savings of 2MB out of 335MB, or 0.6%.
It's not a great tradeoff as-is, but as mentioned our implementation can
be signficantly optimized, and literal dedup will unlock more
opportunities for ICF to identify identical structures that reference
the same literals.

Reviewed By: #lld-macho, gkm

Differential Revision: https://reviews.llvm.org/D103113


int3Jun 11 2021, 4:50 PM
Restricted Project
Differential Revision
D103113: [lld-macho] Deduplicate fixed-width literals
rGb90f9bea9673: Revert "Allow signposts to take advantage of deferred string substitution"