Source-linked AI summary
BOLT: A Practical Binary Optimizer for Data Centers and Beyond
Maksim Panchenko, Rafael Auler, Bill Nell, Guilherme Ottoni
TL;DR
Large, complex data-center applications need effective code-layout optimization, but post-link optimization has been underexplored for modern workloads and profile data is difficult to map back to higher-level representations. The paper presents BOLT, a static LLVM-based post-link optimizer using sample-based profiling, and finds that it improves already optimized binaries while complementing compiler and link-time techniques. Its main scope boundary is that static optimization cannot handle dynamically generated or self-modifying code.
Problem
Large data-center applications make code layout important, while post-link optimization and accurate use of binary-level sample profiles have received limited recent attention.
Method
BOLT is a static, LLVM-based post-link binary optimizer that uses sample-based profiling to optimize code layout.
Results
BOLT improves performance by up to 20.41% on top of FDO and LTO, with gains attributed mostly to more accurate binary-level profile use for code layout.
Takeaways & Limitations
Post-link, compile-time, and link-time optimization strategies are complementary, so combining them can improve performance for large front-end-bound applications.
Takeaways & Limitations
As a static optimizer, BOLT does not handle dynamically generated or self-modifying code, which dynamic binary optimizers can support.
Abstract
from arXiv · showhide
Performance optimization for large-scale applications has recently become more important as computation continues to move towards data centers. Data-center applications are generally very large and complex, which makes code layout an important optimization to improve their performance. This has motivated recent investigation of practical techniques to improve code layout at both compile time and link time. Although post-link optimizers had some success in the past, no recent work has explored their benefits in the context of modern data-center applications. In this paper, we present BOLT, a post-link optimizer built on top of the LLVM framework. Utilizing sample-based profiling, BOLT boosts the performance of real-world applications even for highly optimized binaries built with both feedback-driven optimizations (FDO) and link-time optimizations (LTO). We demonstrate that post-link performance improvements are complementary to conventional compiler optimizations, even when the latter are done at a whole-program level and in the presence of profile information. We evaluated BOLT on both Facebook data-center workloads and open-source compilers. For data-center applications, BOLT achieves up to 8.0% performance speedups on top of profile-guided function reordering and LTO. For the GCC and Clang compilers, our evaluation shows that BOLT speeds up their binaries by up to 20.4% on top of FDO and LTO, and up to 52.1% if the binaries are built without FDO and LTO.
1. Introduction
Large, complex data-center applications make code layout important, while scaling feedback-driven optimization and mapping sampled binary profiles back to compiler representations remain difficult. BOLT addresses this gap with a post-link LLVM optimizer that uses sample-based profiles and complements compiler and link-time optimization.
- Large data-center applications make code locality an important performance target.Their size and complexity create substantial code-layout challenges.
- Sample-based profiling gathers high-quality profiles from unmodified production binaries with minimal operational complexity.This avoids the memory and computational costs that make instrumentation-based profiling difficult to deploy at scale.
- Profile data can be injected at compile time, link time, or post-link time, trading broader optimization access for later-stage accuracy.Earlier injection enables more optimization phases, whereas later injection can better preserve binary-level information for code layout.
- 20.41% performance improvement is achieved on top of FDO and LTO for large real-world applications.The paper attributes most of this improvement to more accurate binary-level use of sample-based profiles for code layout.
- BOLT is a modern open-source post-link optimizer built on LLVM that improves code layout using sample-based profiling.Operating on the binary simplifies profile mapping and supports more accurate low-level optimization.
- Post-link optimization complements compile-time and link-time FDO rather than superseding them.The paper presents these optimization stages as complementary approaches.
2. Motivation
The motivation is to use inexpensive sample-based profiles for code-layout optimization without losing accuracy when mapping binary events to higher-level representations. A static binary optimizer is attractive because it avoids runtime overhead, although it cannot handle dynamically generated or self-modifying code as dynamically optimizing systems can.
- Instrumentation-based profiling complicates builds and imposes significant collection overhead, motivating cheaper sample-based alternatives.Sample-based methods use hardware profile counters and do not require a special instrumented build.
- Sampled profiles may enter the compilation pipeline at source, IR, linker, or post-link levels, creating a trade-off between optimization access and profile accuracy.Earlier stages expose profiles to more optimizations, while later stages retain lower-level information more directly.
- 84.1% profile accuracy after retrofitting to a low-level GCC representation was improved to 92.9% with additional techniques.This quantifies the precision loss associated with mapping profile data back into compiler representations.
- Binary-level events are difficult to map back to higher-level code after transformations such as inlining.The example concerns arranging inlined blocks according to branch frequency to improve prediction and instruction-cache locality.
- Inaccurate branch frequencies can degrade performance, making accurate profile data especially important for code-layout algorithms.Code layout is relatively simple to apply at the binary level, even though low-level profile use limits earlier pipeline optimizations.
- Static binary optimization avoids runtime overhead, whereas dynamic binary optimization can handle dynamically generated and self-modifying code.Dynamic systems may require faster, sub-optimal passes and can degrade performance if not tuned well.
3. Architecture
BOLT is a post-link optimizer designed for large-scale binaries, progressively expanding code coverage while conservatively skipping functions it cannot analyze confidently. Its rewriting pipeline discovers functions, reconstructs CFGs, applies optimizations, and rewrites binaries while preserving required metadata.
- BOLT targets large-scale data-center binaries, including programs exceeding 100 MB of code and containing multiple source languages.
- BOLT incrementally expanded binary code coverage and can optimize some functions while leaving functions that violate its assumptions untouched.
- BOLT initially optimized code layout within existing function boundaries and skipped functions whose control-flow graphs could not be reconstructed with full confidence.
- Relocations Mode: Relocations let BOLT change function order and split function bodies, while an independent post-link design avoids dependence on a particular linker.
- Rewriting Pipeline: The rewriting pipeline discovers functions, retrieves debug and profile data, disassembles functions, builds CFGs, runs optimizations, and rewrites the binary with updated ELF structures.
- BOLT uses LLVM for disassembly and binary modification, benefiting from modularity and support for multiple target architectures.
- BOLT updates DWARF information to reflect code modifications and relocations, and rebuilds CFI for rewritten binaries.
4. Optimizations
BOLT applies compiler-like analyses and transformations focused especially on code layout, while also folding functions and optimizing calls and loads. Its most effective passes directly improve code layout.
- BOLT runs architecture-dependent and architecture-independent passes, supported by dataflow analysis such as register-liveness checking.
- BOLT’s instruction-space passes trade optional instruction choices for I-cache space by removing alignment NOPs, AMD-friendly REPZ bytes, or using shorter instructions.
- Code Size: BOLT’s binary-level identical code folding optimizes functions without -ffunction-sections and functions containing jump tables.For HHVM, BOLT reduced code size by about 3% on top of the linker’s ICF pass.
- Call Optimizations: BOLT uses call-frequency information for indirect call promotion, limited small-function inlining, and PLT call optimization.
- Load Optimization: BOLT may replace loads from statically known read-only values with immediate loads, but aborts when the new encoding is larger than the original.
- Code Layout: BOLT reorders basic blocks along frequently executed paths so hot successors are likely fall-throughs, reducing taken branches and branch-predictor pressure.
- Code Layout: BOLT’s HFSort function reordering primarily improves I-TLB performance, and together with hot/cold block reordering, these are its most effective passes.
5. Profiling Techniques
BOLT relies on sample-based profiling, particularly LBR data, to obtain branch and call information for code-layout optimization. LBRs improve resilience to sampling bias, although collected profiles can still violate flow consistency.
- Sample-based profiling techniques have pitfalls and caveats when producing accurate profiling data.
- LBR Profiling: LBRs record the last 32 taken branches and provide accurate critical-edge counts that basic-block counts cannot infer.
- LBR Profiling: For a workload with a 5.4% BOLT speedup, performance differences across tested LBR sampling events and PEBS levels stayed within 1%.
- Block Layout: Under worst-case sample bias, LBRs preserve the executed path leading to a sampled block, whereas non-LBR samples reveal only a hot block without its incoming path.
- Profile Reconstruction: LBR profiles can contradict flow equations because LBRs store taken branches rather than complete execution-flow information.
- Function Reordering: BOLT uses HFSort with LBR-derived call-graph edge weights, or builds an incomplete call graph from direct calls and sampled blocks without LBRs.
6. Evaluation
BOLT was evaluated on Facebook data-center binaries and improved performance across the workload set, with benefits linked to code layout and microarchitectural locality.
- BOLT was evaluated on five Facebook data-center binaries, including HHVM, TAO, Proxygen, and two Multifeed services.
- BOLT applied on top of HFSort produced speedups in every Facebook workload, averaging 5.4% and reaching 8.0% for HHVM.HHVM was also built with LTO in this comparison.
- HHVM’s large code size makes it front-end bound and particularly amenable to BOLT’s code-layout optimizations.
- HHVM’s code-layout improvements reduced branch misses by 11% and first-level instruction-cache misses by 18%.BOLT also produced smaller improvements in data-cache and TLB-related metrics.
6.2 Clang and GCC Compilers
BOLT was tested on Clang and GCC compiler binaries alongside PGO and LTO configurations. It substantially improved build performance, including on binaries already optimized with profile and link-time information.
- Clang Setup: The Clang evaluation used instrumented profiling followed by a PGO+LTO build, while BOLT consumed perf-derived profiles for post-link optimization.
- Experimental Results: BOLT improved full-build performance for both Clang and GCC evaluations across configurations with and without profile-guided optimization.The evaluation used compiler builds and full Clang builds as benchmarks.
- Experimental Results: 7.45% speedup was measured for a full Clang build on top of GCC with PGO.
- Experimental Results: BOLT reduced taken branches by 44.3% over PGO+LTO and by 69.8% over the baseline.The paper associates this reduction with improved instruction-cache locality.
6.3 Analysis of Suboptimal Compiler Code Layout
Analysis of Clang binaries found that suboptimal layouts frequently arose from inlining, leaving cold blocks interleaved with hot blocks even after LTO and PGO.
- BOLT’s layout diagnostics identified frequently executed functions containing cold basic blocks interleaved with hot blocks in Clang’s LTO+PGO binary.
- BOLT reports optimization statistics for both Clang’s baseline and PGO+LTO binaries.
- Most analyzed suboptimal layouts originated from function inlining, which can make a block cold at a particular inlined call site.Figure 10 illustrates this pattern at the binary level using execution counts.
6.4 Heat Maps
Heat maps compare instruction-memory access patterns before and after BOLT, showing hot-code packing into a much denser address range while conservatively leaving some complex functions less reorganized.
- Heat Maps: The HHVM heat maps plot instruction-address accesses for the regular binary and the BOLT-processed binary using logarithmically scaled profiling counts.White areas indicate unsampled cold blocks, while stronger red indicates more frequently accessed instruction memory.
- Heat Maps: Indirect tail calls limited BOLT’s processing because their targets may be other functions or basic blocks within the same function.BOLT left these non-simple functions untouched, leaving some cold blocks in the hot area.
- Heat Maps: Function splitting and reordering moved cold blocks away from hot code, benefiting instruction-cache and instruction-TLB locality.
6.5 Importance of LBR
LBRs improve BOLT’s profiling accuracy, with the largest benefit appearing in basic-block layout because it requires fine-grained basic-block profiles.
- LBR impact: About 2% of HHVM’s total CPU-time improvement from BOLT comes from using LBRs for more accurate profiling.The overall BOLT improvement is about 8%, while LBRs account for about 2%.
- LBR impact: LBRs reduce executed instructions by 0.35% in the evaluated HHVM dataset.
- Why LBRs matter: LBRs matter more for basic-block layout than function reordering because basic-block optimization needs finer-grained profiling.Without LBRs, obtaining profiles at basic-block level is harder.
7. Related Work
Related work spans dynamic and static binary optimization, architecture-specific rewriting, and profile-guided compiler optimization. The paper positions BOLT alongside these approaches rather than as a replacement for them.
- Binary optimization: Binary optimization includes static optimizers that act before execution and dynamic optimizers that act during execution.DynamoRIO and QEMU are cited as platforms for prototyping dynamic binary optimization.
- Static optimization: Static binary optimizers typically target low-level transformations using precise information about the host architecture.The related work includes architecture-specific examples such as MAO and Ispike.
- Profile-guided optimization: Profile-guided compiler optimization uses runtime information, as in AutoFDO, while BOLT performs related layout optimization after linking.The paper reports that gains from general FDO and BOLT can be complementary and used together.
8. Conclusion
BOLT reorganizes large applications’ code to reduce pressure on hardware structures, using post-link profiling to optimize beyond what the compiler can achieve alone. Experiments report gains on data-center applications and open-source compilers, with the approaches combining rather than simply overlapping.
- Conclusion: BOLT targets large binaries whose code can pressure caches, TLBs, and branch predictors.Its main goal is to reorganize application code to reduce that pressure.
- Conclusion: A post-link optimizer can use profiling from the binary level to perform optimizations beyond what a compiler can achieve.
- Results: Facebook data-center applications improve by 2% to 8% with BOLT.
- Results: BOLT improves Clang performance by 15% on top of LTO and FDO, while its strengths combine with compiler optimization rather than purely overlap.