At warehouse scale a 1% speedup spans tens of millions of cores, and the best remaining 1–8% hides in code layout that only post-link profiles can see — but the reigning binary optimizer needed up to 73 GB of RAM, disassembled CISC binaries inexactly, and crashed three of four Google applications at startup; Propeller never disassembles — it RELINKS, mapping hardware profiles to basic blocks via compiler-emitted metadata, regenerating only the ~10% of object files containing hot code, and letting the linker order novel "basic block sections" — all inside the distributed build system's 12 GB action limits, at +1% binary size, in production.
The argument in one glance
-
Problem
The last few percent live below the compiler
Warehouse-scale applications make single-digit speedups enormous in absolute terms — and the mature toolchain already deploys profile-guided optimization and link-time optimization everywhere. Yet profiles injected at compile time DECAY: as inlining, and every later transformation reshapes the code, the profile-to-code mapping blurs, leaving mislaid basic blocks, poorly split functions, and frontend stalls (icache and iTLB misses) that only measurements of the FINAL binary can fix. BOLT proved the prize is real: injecting hardware profiles post-link improved large Facebook workloads by 2–7% beyond PGO+LTO.
-
What people did
Disassemble the binary and rewrite it
Post-link optimizers like BOLT reconstruct the control-flow graph by disassembling the executable, apply layout optimizations, and rewrite the binary. Lightning BOLT parallelized parts of the pipeline, and the approach became the state of the art for squeezing out the post-PGO remainder.
-
Why it fell short
Disassembly and monoliths don't survive warehouse scale
Warehouse binaries are statically linked, maximally optimized, and salted with hand-written assembly — exactly where CISC disassembly is least exact. Measured on Google's applications: BOLT's profile conversion peaked at 24–73 GB of RAM (distributed-build actions get 12 GB), its key stages serialize on one machine, optimized binaries grew ~45%, couldn't be stripped, broke restartable-sequence and FIPS-140 integrity-check code — and three of four warehouse applications CRASHED at startup. Building on a beefy workstation instead isn't an option either: untrusted build environments fail software supply-chain requirements.
-
This paper's idea
Don't rewrite the binary — relink it
Propeller re-imagines post-link optimization for distributed builds. The compiler emits a Basic Block Address Map (an unloaded ELF section) so production hardware profiles map to basic blocks WITHOUT disassembly; a lightweight whole-program analysis (under 3 GB even for 600 MB of text) computes an Ext-TSP layout; then the build system regenerates just the ~10% of object files containing hot code — as ordinary distributed compiler actions emitting novel BASIC BLOCK SECTIONS — reuses cached cold objects, and relinks with a symbol-ordering file. Relinking is cheaper than the original link (35% on average), binaries grow ~1%, and performance improves 1.1–8% beyond PGO+ThinLTO. Deployed at Google: tens of millions of cores run Propeller-optimized code at any moment.
Why this problem is worth solving
The economics are the datacenter-tax argument in its purest form:
when one binary occupies fleet-scale core counts, a 1% speedup is
a hardware budget line, so operators (this paper is Google’s
compiler team; BOLT is Meta’s) chase percents that would be
rounding errors elsewhere. The mature answers are already
deployed —
profile-guided optimization: build an instrumented
binary (or sample production with hardware counters, as AutoFDO
does), collect branch weights and call frequencies, then rebuild
with the profile steering inlining, block layout, and register
allocation. Worth ~5% on standard benchmarks and universal at
warehouse scale
LLVM’s scalable link-time optimization:
per-module summaries enable cross-module optimization (especially
inlining) without the monolithic classic-LTO link that loads
every module’s IR into one process — the design whose
distributed-build-friendly shape Propeller explicitly
imitates
What makes this a systems paper rather than a compiler-pass paper is the constraint set. Google’s distributed build system runs 15M+ actions daily under fixed budgets (~1 core, 12 GB per action), with content-addressed caching above 90% hit rates; release pipelines demand trusted, reproducible builds. The incumbent post-link technology violates every one of those constraints at once. Propeller’s contribution is less any single optimization than a demonstration of how to re-architect an optimization class — the way ThinLTO re-architected LTO — so it composes with the infrastructure that warehouse-scale software actually uses.
What people did before, and where it broke
- BOLT / Lightning BOLT (Meta): the breakthrough that revived post-link optimization — disassemble, rebuild the CFG, re-lay-out with the Ext-TSP algorithm, rewrite. On warehouse binaries it hits four walls. Memory: profile conversion peaked at 24, 36, and 73 GB on Google’s larger apps — versus 12 GB action limits (24 GB for the largest). Serialization: function discovery, disassembly, global optimization, and emit-and-link are single-machine, sequential stages — over half of total runtime. Soundness: disassembly is an inexact science on x86 — data embedded in code, hand-tuned assembly — and rewriting breaks restartable sequences, FIPS-140 startup integrity checks, and binary stripping; three of four Google warehouse apps crashed at startup. Size: metadata builds +20–60%, optimized binaries +45% (and a debug clang’s required relocation section alone is 43% of a 1.7 GB binary).
- Workstation builds as a workaround fail differently: a 192 GB developer machine can run BOLT, but untrusted build environments are disqualified by supply-chain verifiability and insider-risk programs.
- Classic full LTO shares the monolith disease (whole-program IR in one process), which is exactly why ThinLTO exists — the precedent Propeller generalizes to post-link optimization.
- CodeStitcher and kin do inter-procedural layout inside full LTO, inheriting its scalability limits; older binary optimizers (Spike, ALTO, FDPR…) predate profile-guided, distributed-build reality.
How Propeller works
Four phases, all inside the distributed build system
-
Phase 1: compile & cache optimized IR
Modules compile to fully-optimized LLVM IR (PGO applied) and are cached by the build system — with ThinLTO in use, this phase adds NOTHING new. The cache is the foundation: later phases reprocess a small targeted fraction of artifacts instead of the world.
-
Phase 2: link with a Basic Block Address Map new
The backend emits, per function, an unloaded ELF section recording each machine basic block's offset and ID (plus fall-through hints). This metadata — the disassembly replacement — costs 7–9% binary size on disk, zero at runtime, and lets ANY later tool map virtual addresses back to compiler-known basic blocks.
-
Phase 3: profile + whole-program analysis, lightweight by design new
Linux perf collects Last Branch Records (source/destination pairs of retired jumps) from the PGO binary under production-representative load. Samples map through the address map onto machine basic blocks; a dynamic CFG is built incrementally — no instructions ever decoded. Ext-TSP computes the layout, emitting per-function cluster directives (cc_prof.txt) and a global symbol order (ld_prof.txt). Peak memory: ≤2.6 GB even for Superroot's 598 MB of text — versus BOLT's 73 GB.
-
Phase 4: distributed re-codegen + relink new
Most object files are entirely cold (83–95%) and are reused from cache untouched. The ~10% with hot functions rerun their LLVM backends — ordinary distributed compiler actions — emitting basic block CLUSTER sections per the layout directives. The linker then orders all sections by the symbol-ordering file and drops the metadata. Relinking is CHEAPER than the baseline link: 35% on average, up to 61%.
-
Basic block sections: the linker abstraction new
Where function sections gave linkers function-granularity layout, basic block sections put one or MORE basic blocks in their own named text section — making fine-grained layout a linker feature rather than a binary-rewriting feat. Clustering (hot blocks in the primary section keeping the function's symbol; cold blocks in a .cold section; more clusters when inter-procedural layout pays) bounds the overhead that per-block sections would explode (clang: 2.1M blocks vs 160K functions).
-
The engineering below the abstraction new
Reorderable blocks need explicit fall-through jumps with relocations (a linker relaxation pass later deletes redundant ones and re-shrinks branch encodings); DWARF debug info uses discontiguous address ranges per cluster; CFI frame descriptors are emitted per fragment (clusters amortize .eh_frame growth); C++ exception call-site tables split per section, with a nop guarding the landing-pad-at-offset-zero ambiguity. The result: optimized binaries just ~1% larger, fully debuggable, strippable, and sound.
The idea
Replace disassembly with a forwarding address. Everything painful about post-link optimization flows from reconstructing compiler knowledge that the compiler had and threw away. The Basic Block Address Map simply keeps it: a few unloaded bytes per block mapping final addresses back to machine basic blocks. With that, hardware samples resolve to compiler IR without decoding one instruction — the whole-program analysis becomes a graph computation over sample data (≤3 GB where BOLT needs up to 73 GB), and soundness stops being probabilistic: nothing is ever reconstructed, so hand-written assembly, embedded data, restartable sequences, and integrity-checked crypto modules are never misparsed — they’re simply left alone.
Relinking turns a monolithic optimizer into build actions. The ThinLTO lesson, reapplied: split the optimization into a cheap serial whole-program step and distributed per-module steps. The serial part (Phase 3) only decides — layout directives in, text files out. The heavy part — regenerating code with new layouts — is ordinary compiler backend invocations, parallelized by the build system that already exists, on the ~10% of objects that contain any hot code; the cold 90% comes from cache byte-identical. Even the final link gets cheaper than the baseline’s, because so much is cached. The contrast with BOLT on a workstation is honest and instructive: BOLT is 2–4× faster there — monoliths win on one big machine — but the warehouse constraint set (12 GB actions, trusted builders, mandatory caching) is precisely where the monolith cannot go.
Make layout a linker feature, and heuristics dissolve. Basic block sections are the enabling abstraction: once blocks (or clusters of them) are named, relocatable sections, a symbol ordering file expresses arbitrary layouts — hot/cold splitting, discontiguous functions, inter-procedural interleaving — as linking, not rewriting. The clearest payoff is function splitting: LLVM’s prior implementation extracted cold blocks behind a function call, whose overhead demanded a profitability heuristic; with sections, a function body is simply discontiguous, cost-free, no heuristic needed — measured ~2× more effective, with up to 40% iTLB and 5% icache miss reductions. The same machinery reaches further when profitable: splitting a multi-modal function so each hot loop sits beside its callee (inter-procedural layout, +0.8% on clang beyond intra-function) — expressible only because layout granularity dropped below the function.
Optimizing a warehouse binary, phase by phase
Search (413 MB of text, 18M basic blocks) through Propeller
LBR = Last Branch Records, the CPU's ring buffer of recent taken jumps, sampled by Linux perf. Ext-TSP = the layout algorithm (from BOLT's lineage) maximizing fall-through of hot edges. Cluster = a group of basic blocks sharing one section. Numbers from the paper's evaluation; baseline is PGO + ThinLTO.
Step 1 of 7
Build as usual — plus a map
The binary builds with full PGO and ThinLTO through the distributed build system; the only change is the Basic Block Address Map section recording every block's offset and ID. Binary grows 7–9% on disk; nothing changes at runtime since the section is never loaded.
metadata = the disassembly replacement with ThinLTO already in use, phases 1–2 add no new compute
Why it works
- Profiles decay through optimization, so the final binary is the only truthful measurement target → sampling the PGO-optimized binary and re-deciding layout recovers what compile-time injection lost → 1.1–8% beyond an already-PGO+ThinLTO baseline, concentrated in frontend stalls (icache, iTLB, branch resteers).
- Compiler-emitted address maps preserve what disassembly tries to reconstruct → profile mapping becomes exact and cheap, and soundness hazards (embedded data, hand assembly, rseq, FIPS checks) vanish because nothing is reparsed → zero startup crashes where BOLT lost three of four applications.
- Hot code is rare (5–17% of objects on these workloads) and caching is ubiquitous → regenerating only hot objects as distributed actions, reusing everything else, makes the optimizer’s marginal cost small — relinking beats the baseline link by 35% → the optimization fits inside 12 GB action limits that the monolith exceeds 6-fold.
- Sections are the linker’s native unit → naming basic block clusters as sections turns arbitrary fine-grained layout into a symbol-ordering problem lld already solves → function splitting loses its call-stub overhead and its heuristic (~2× more effective), and discontiguous, inter-procedurally interleaved functions become expressible.
- Splitting the optimizer ThinLTO-style — tiny serial decision step, distributed heavy steps — matches the shape of the infrastructure → trusted builds, caching, and parallelism come free from the build system instead of being reimplemented.
What it costs
- Layout only. Propeller’s gains are purely code layout; BOLT’s disassembly-level extras (peephole rewrites, PLT optimizations) explain its 1% edge on Search. Post-link software prefetch insertion is sketched as future Propeller work.
- A metadata build and a second pipeline. Binaries carry 7–9% metadata during profiling; the full profile-analyze-relink cycle extends build-release time by ~78% on average (Propeller’s own compute is ~18% of that — profiling and rebuild logistics dominate).
- Worse on one workstation. BOLT rewrites clang-sized binaries 2–4× faster on a big machine; Propeller’s advantages are contingent on the distributed-build context it was designed for.
- Small-program regressions. On SPEC2017, both tools regress ~5 benchmarks (Propeller by 0.8–3.9%): layout changes disturb the decoded-stream buffer (DSB misses +12%), and tuning for small programs is explicitly future work — this is a warehouse-scale tool.
- Inter-procedural layout is nascent. The headline results use intra-function layout; the inter-procedural mode costs 3–10× more analysis time for +0.8% (clang) and awaits a fuller study.
- Source and toolchain required. Relinking needs the build graph, IR cache, and LLVM backend — BOLT’s ability to optimize third-party binaries without source has no Propeller equivalent.
The evaluation
Baselines are strong (instrumented PGO + ThinLTO), profiles identical across tools, and the comparison spans six large applications (clang, MySQL, and four Google warehouse workloads from 26 MB to 598 MB of text) plus SPEC2017. The evaluation’s structure mirrors the thesis: memory against build-system limits, soundness against production binaries, size against release constraints, performance against the state of the art — and a frank section on what it took to evaluate BOLT at all.
Squeezing the post-PGO remainder, three ways
| Property | PGO + ThinLTO (deployed baseline) | BOLT (disassemble & rewrite) | Propeller (map & relink) |
|---|---|---|---|
| How late profiles reach the code | |||
| Peak memory (profile conversion / analysis) | — | ||
| Soundness on warehouse binaries | Sound by construction | ||
| Binary size | Baseline | ||
| Performance (beyond PGO+ThinLTO) | The bar |
Check yourself
Check your understanding
1. The baseline already uses profile-guided optimization — profiles steered inlining and layout during compilation. Predict why sampling the FINAL binary and re-optimizing post-link still yields 1–8%.
2. Propeller's central architectural bet is eliminating disassembly. What does the Basic Block Address Map replace it with, and why does this single change fix both the MEMORY problem and the SOUNDNESS problem?
3. On a 72-core workstation, BOLT optimizes binaries 2–4× FASTER than Propeller. Why does Google deploy Propeller anyway?
4. Basic block sections made LLVM's function-splitting optimization ~2× more effective — by REMOVING a heuristic. What changed?