<div dir="auto">Hello,<div dir="auto"><br></div><div dir="auto">Thanks for your work on bolt. We tried to use it to speedup clang itself following the instructions in your github repo. </div><div dir="auto"><br></div><div dir="auto">The main problem we ran into with pref not being able to run on our AMD workstations nor in our VMs in the cloud. I know it's not exactly bolt related but are there other ways to generate this profile? Ideally we would collect data while building our app as part of our toolchain builder in the CI (as we do with PGO) - but I was not able to get this working with the perf tool. </div><div dir="auto"><br></div><div dir="auto">Thanks for your help.</div><div dir="auto">Tobias</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, Oct 20, 2020, 20:39 Maksim Panchenko via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div lang="EN-US" link="#0563C1" vlink="#954F72" style="word-wrap:break-word">
<div class="m_-1006572403267135739WordSection1">
<p style="margin:0in"><span style="color:#0e101a">Hi All,<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"><u></u> <u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a">Please find below an RFC for adding a binary optimization framework to LLVM.<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"><u></u> <u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a">Thanks for the feedback,<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a">Maksim & BOLT Team<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"><u></u> <u></u></span></p>
<h1 style="margin:0in"><span style="color:#0e101a;font-weight:normal">[RFC] BOLT: A Framework for Binary Analysis, Transformation, and Optimization<u></u><u></u></span></h1>
<p style="margin:0in"><span style="color:#0e101a"><u></u> <u></u></span></p>
<h2 style="margin:0in"><span style="color:#0e101a;font-weight:normal">1. Background and Motivation<u></u><u></u></span></h2>
<p style="margin:0in"><span style="color:#0e101a"><u></u> <u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a">BOLT is a static post-link binary optimizer successfully used inside and outside of Facebook for code optimizations that complement traditional compiler whole-program and link-time optimizations [1]. Last year
Google reported that BOLT accelerates their key workloads by 2% to 6% [2]. Additionally, BOLT is used in academia as a framework for program instrumentation, transformation, and binary analysis [3].<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"><u></u> <u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a">We believe that including BOLT in the LLVM project will benefit the community in several ways [4]. First, BOLT is useful as a binary optimizer. It has been used at Facebook to accelerate the top services, and
we would love to see more people benefit from the performance boost that BOLT brings. We would also love to see our partners adopt BOLT's new use-cases, such as optimizing mobile and embedded applications. Beyond the binary optimizer, BOLT is an impressive
infrastructure that enables research in the following areas:<u></u><u></u></span></p>
<ul style="margin-top:0in" type="disc">
<ul style="margin-top:0in" type="disc">
<li class="m_-1006572403267135739ql-indent-1" style="color:#0e101a;margin-top:0in;margin-bottom:0in">
Advanced disassembly<u></u><u></u></li><li class="m_-1006572403267135739ql-indent-1" style="color:#0e101a;margin-top:0in;margin-bottom:0in">
Low-level program instrumentation<u></u><u></u></li><li class="m_-1006572403267135739ql-indent-1" style="color:#0e101a;margin-top:0in;margin-bottom:0in">
Static analysis<u></u><u></u></li></ul>
</ul>
<p style="margin:0in"><span style="color:#0e101a"><u></u> <u></u></span></p>
<h2 style="margin:0in"><span style="color:#0e101a;font-weight:normal">2. Overview<u></u><u></u></span></h2>
<p style="margin:0in"><span style="color:#0e101a"><u></u> <u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a">While BOLT uses several LLVM libraries [5], it is currently a separate project based on an out-of-tree version of LLVM [6]. Most of the code lives under separate tools/llvm-bolt directory, and required changes
to LLVM are included in the supplied patch [7]. The patch mainly consists of backported fixes and minor extensions of the existing interfaces to update debug info, frame information, and ORC.<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"><u></u> <u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a">BOLT has no external build dependencies outside of LLVM. For profile collection, we recommend using sampling with a Linux perf tool [8]. LBR (last branch records) feature [9] is recommended as it improves profile
quality dramatically. BOLT can be supplied perf.data profile directly, but in general, we advise converting the profile first using the supplied perf2bolt utility. In case the sampling profiling is unavailable, e.g., while running under a hypervisor locally
or in the cloud, BOLT provides a builtin instrumentation.<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"><u></u> <u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a">BOLT supports x86-64 ELF as the primary platform. We have also implemented the initial support for Aarch64, and the support for MachO is in the works.<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"><u></u> <u></u></span></p>
<h2 style="margin:0in"><span style="color:#0e101a;font-weight:normal">3. USE CASES<u></u><u></u></span></h2>
<p style="margin:0in"><span style="color:#0e101a"><u></u> <u></u></span></p>
<h2 style="margin:0in"><span style="color:#0e101a;font-weight:normal">3.1 Link-time and binary transformations and optimizations<u></u><u></u></span></h2>
<p style="margin:0in"><span style="color:#0e101a"><u></u> <u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a">Static profile-driven post-link optimization of an application was our primary goal when creating BOLT. The convenience and expandability that the model offers perhaps could only be exceeded by a dynamic binary
optimization approach. E.g., to optimize a binary using a perf-generated profile, the user has to execute a single command:<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"><u></u> <u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a">$ llvm-bolt a.out -data perf.data -o a.out.bolt <optimization opts><u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"><u></u> <u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a">No recompilation of a.out is needed (*), but we ask to link with "--emit-relocs" for maximum performance gains. However, the latter is not a strict requirement, and the command works even on stripped binaries.<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"><u></u> <u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a">We have worked on reducing BOLT processing time and memory consumption. Overall, BOLT efficiency has been improved by over 3X during that process. It takes less than a minute to optimize HHVM [10] production
binary with over 100 MB of code and less than 3 minutes to optimize another multi-gigabyte production binary with 500 MB of code. BOLT memory consumption is under 5 GB for HHVM and under 13 GB for the large binary (**).<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"><u></u> <u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a">Fast turn-around times for optimizing an application with BOLT without the need for source code allow us to design a system that automatically manages binary profiling and optimization. This is one of the most
exciting directions in application optimization we are currently pursuing.<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"><u></u> <u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a">We thought it would be interesting to perform a fresh comparison of BOLT overhead to Propeller [11]. Sadly, Propeller relies on a custom version of an external create-llvm-prof tool that we could not build in
our setup, and using a GitHub-hosted binary version of that tool in the virtual environment produced a profile that caused a performance regression of the optimized application. Using "-fbasic-block-sections=all" Propeller option without a profile resulted
in fast linking times but also caused a performance regression.<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"><u></u> <u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a">Although code reordering is the primary optimization in BOLT and the source of most performance gains, it is not the only optimization in BOLT. The full list of optimizations includes late inlining, indirect
call promotion, frame optimizations, and others. The convenience of adding new optimizations in whole-program post-link mode is one of the main advantages that the BOLT framework offers, be it for research or practical purposes.<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"><u></u> <u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a">Additionally, BOLT can add new code to a linked ELF binary. We have recently used that capability to allocate frequently-executed code on huge pages automatically. Even legacy applications can now use 2MB pages
for code on x86-64 Linux systems to reduce the number of iTLB misses.<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"><u></u> <u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a">BOLT's ability to process and optimize binary code without source code, such as legacy/distributed binaries, or code from third-party and assembly-written code, provides another advantage over a pure compiler-based
approach. This advantage could or could not be important for optimizations depending on the user scenario. However, the visibility into the code mentioned above could be critical for other code re-writing cases such as vulnerability mitigations, instrumentation,
and static analysis.<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"><u></u> <u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a">*) Support for input with split functions is in the works. Before it is completed, we ask not to use "-freorder-blocks-and-partition" compiler option during the build. A similar or better result will be achieved
by running the BOLT function splitting pass.<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"><u></u> <u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a">**) while running BOLT with "-reorder-blocks=cache+ -reorder-functions=hfsort -split-functions=1 -split-eh" optimization options. DWARF update takes extra time and memory.<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"><u></u> <u></u></span></p>
<h2 style="margin:0in"><span style="color:#0e101a;font-weight:normal">3.2 Advanced Disassembly<u></u><u></u></span></h2>
<p style="margin:0in"><span style="color:#0e101a"><u></u> <u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a">Internally, BOLT identifies code in the binary, breaks it into functions, disassembles, and uses static analysis to build a control flow graph. This functionality could complement a traditional disassembler,
as it adds the ability to display possible targets for indirect jumps/calls, providing a better understanding of the control flow in a function.<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"><u></u> <u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a">Additionally, for performance analysis, the disassembly is annotated with execution counts, including those for indirect branch targets within a function (jump tables) and across functions (indirect and virtual
function calls). E.g.:<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"><u></u> <u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"> <Basic Block> .LFT35985<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"> Exec Count : 42<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"> Predecessors: .Ltmp935657<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"> 00003c8b: leaq "JUMP_TABLE/foo/1.14"(%rip), %rcx<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"> 00003c92: movslq (%rcx,%rax,4), %rax<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"> 00003c96: addq %rcx, %rax<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"> 00003c99: jmpq *%rax # JUMPTABLE @0x6e0f94<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"> Successors: .Ltmp935702 (count: 0, mispreds: 0),<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"> .Ltmp935705 (count: 41, mispreds: 26),<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"> .Ltmp935703 (count: 0, mispreds: 0),<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"> .Ltmp935704 (count: 1, mispreds: 0)<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a">....<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"> <BasicBlock>.LFT43 (9 instructions, align : 1)<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"> Exec Count : 8<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"> Predecessors: .LBB01191<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"> 00000028: movq %rdx, %rbx<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"> 0000002b: leaq 0x20(%rsp), %rdi<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"> 00000030: movl $0x2, %edx<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"> 00000035: movq %rbx, %rsi<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"> 00000038: callq *%rax # CallProfile: 8 (8 mispreds) :<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"> { f1: 3 (3 mispreds) },<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"> { f2: 1 (1 mispreds) },<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"> { f3: 4 (4 mispreds) }<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"> 0000003a: movdqu 0x10(%rbx), %xmm0<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"> 0000003f: movdqu %xmm0, 0x30(%rsp)<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"> 00000045: movq %xmm0, %rcx<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"> 0000004a: jmp .Ltmp26968<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"> Successors: .Ltmp26968 (count: 8, mispreds: 0)<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"><u></u> <u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a">With LLVM integration, the advanced disassembler can be added as a new standalone tool or as an extra feature to existing tools such as <em><span style="font-family:"Calibri",sans-serif">llvm-objdump</span></em>.<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"><u></u> <u></u></span></p>
<h2 style="margin:0in"><span style="color:#0e101a;font-weight:normal">3.3 Low-Level Program Instrumentation<u></u><u></u></span></h2>
<p style="margin:0in"><span style="color:#0e101a"><u></u> <u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a">Tools, such as memory sanitizers, rely on compiler-generated memory instrumentation to detect application errors at runtime. Suppose part of the application is written in assembly or comes from a library with
no sources. In that case, such code could become a source of false positives and false negatives depending on the memory access types missed by the instrumentation. Since BOLT can instrument arbitrary code, independent of the source, it can complement compiler-based
instrumentation and fill in the missing parts leading to a higher quality signal from the tool.<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"><u></u> <u></u></span></p>
<h2 style="margin:0in"><span style="color:#0e101a;font-weight:normal">3.4 Static Analysis<u></u><u></u></span></h2>
<p style="margin:0in"><span style="color:#0e101a"><u></u> <u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a">BOLT offers an intuitive API to perform compiler-level analyses directly on machine code. Because BOLT reconstructs the control-flow graph of the program, it allows pass writers to extract arbitrary information
beyond the scope of a single basic block with data-flow analyses. As an example, we can perform shrink wrapping by checking how stack-accessing instructions are using the frame in a given function and validating opportunities to move memory accesses in hot
basic blocks to colder areas.<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"><u></u> <u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a">While this framework provides the optimization writer with greater reach over previously opaque external third-party binary code linked in the binary, perhaps the greatest value of this is in this code being
visible at all. With static analysis, users can write passes to draw conclusions on safety concerns as well, such as checking if system or library calls are being used in a suspicious way without the need to execute the binary.<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"><u></u> <u></u></span></p>
<h2 style="margin:0in"><span style="color:#0e101a;font-weight:normal">4. Plans<u></u><u></u></span></h2>
<p style="margin:0in"><span style="color:#0e101a"><u></u> <u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a">BOLT is a mature project that has been used in production for years, but we continue to develop BOLT and invest in new use-cases and optimizations. Below is a shortlist of areas that are currently under development:<u></u><u></u></span></p>
<ol style="margin-top:0in" start="1" type="1">
<li class="MsoNormal" style="color:#0e101a">Automatic profile collection and optimization<u></u><u></u></li><li class="MsoNormal" style="color:#0e101a">MachO support<u></u><u></u></li><li class="MsoNormal" style="color:#0e101a">LLD integration<u></u><u></u></li><li class="MsoNormal" style="color:#0e101a">Optimizing Linux kernel<u></u><u></u></li></ol>
<p style="margin:0in"><span style="color:#0e101a"><u></u> <u></u></span></p>
<h2 style="margin:0in"><span style="color:#0e101a;font-weight:normal">--<u></u><u></u></span></h2>
<p style="margin:0in"><span style="color:#0e101a">BOLT Team<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"><u></u> <u></u></span></p>
<h2 style="margin:0in"><span style="color:#0e101a;font-weight:normal">References<u></u><u></u></span></h2>
<p style="margin:0in"><span style="color:#0e101a">[1] Maksim Panchenko, Rafael Auler, Bill Nell, and Guilherme Ottoni. 2019. BOLT: a practical binary optimizer for data centers and beyond. In "Proceedings of the 2019 IEEE/ACM International Symposium on Code
Generation and Optimization" (CGO 2019). IEEE Press, 2–14. <a href="https://research.fb.com/publications/bolt-a-practical-binary-optimizer-for-data-centers-and-beyond/" target="_blank" rel="noreferrer"><span style="color:#4a6ee0">https://research.fb.com/publications/bolt-a-practical-binary-optimizer-for-data-centers-and-beyond/</span></a><u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a">[2] <a href="https://lists.llvm.org/pipermail/llvm-dev/2019-September/135393.html" target="_blank" rel="noreferrer"><span style="color:#4a6ee0">https://lists.llvm.org/pipermail/llvm-dev/2019-September/135393.html</span></a><u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a">[3] Joe Savage and Timothy M. Jones. 2020. HALO: post-link heap-layout optimisation. In "Proceedings of the 18th ACM/IEEE International Symposium on Code Generation and Optimization" (CGO 2020). Association
for Computing Machinery, New York, NY, USA, 94–106. DOI:<a href="https://doi.org/10.1145/3368826.3377914" target="_blank" rel="noreferrer"><span style="color:#4a6ee0">https://doi.org/10.1145/3368826.3377914</span></a><u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a">[4] <a href="https://github.com/facebookincubator/BOLT/issues/46" target="_blank" rel="noreferrer"><span style="color:#4a6ee0">https://github.com/facebookincubator/BOLT/issues/46</span></a><u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a">[5] Maksim Panchenko. 2016. Building Binary Optimizer with LLVM. 2016 European LLVM Developers' Meeting. <a href="https://llvm.org/devmtg/2016-03/#presentation7" target="_blank" rel="noreferrer"><span style="color:#4a6ee0">https://llvm.org/devmtg/2016-03/#presentation7</span></a><u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a">[6] <a href="https://github.com/facebookincubator/BOLT" target="_blank" rel="noreferrer"><span style="color:#4a6ee0">https://github.com/facebookincubator/BOLT</span></a><u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a">[7] <a href="https://github.com/facebookincubator/BOLT/blob/master/llvm.patch" target="_blank" rel="noreferrer">https://github.com/facebookincubator/BOLT/blob/master/llvm.patch</a><u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a">[8] perf: Linux profiling with performance counters. <a href="https://perf.wiki.kernel.org/index.php/Main_Page" target="_blank" rel="noreferrer">https://perf.wiki.kernel.org/index.php/Main_Page</a>.<u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a">[9] Runtime Performance Optimization Blueprint: Intel® Architecture Optimizations with LBR. <a href="https://software.intel.com/content/www/us/en/develop/articles/runtime-optimization-blueprint-IA-optimization-with-last-branch-record.html" target="_blank" rel="noreferrer"><span style="color:#4a6ee0">https://software.intel.com/content/www/us/en/develop/articles/runtime-optimization-blueprint-IA-optimization-with-last-branch-record.html</span></a><u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a">[10] The HipHop Virtual Machine. <a href="https://hhvm.com/" target="_blank" rel="noreferrer">https://hhvm.com/</a><u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a">[11] Propeller RFC. <a href="https://github.com/google/llvm-propeller/blob/plo-dev/Propeller_RFC.pdf" target="_blank" rel="noreferrer">https://github.com/google/llvm-propeller/blob/plo-dev/Propeller_RFC.pdf</a>. Updated performance results: <a href="https://lists.llvm.org/pipermail/llvm-dev/2019-October/136030.html" target="_blank" rel="noreferrer">https://lists.llvm.org/pipermail/llvm-dev/2019-October/136030.html</a><u></u><u></u></span></p>
<p style="margin:0in"><span style="color:#0e101a"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt"><u></u> <u></u></span></p>
</div>
</div>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org" target="_blank" rel="noreferrer">llvm-dev@lists.llvm.org</a><br>
<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev" rel="noreferrer noreferrer" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</blockquote></div>