<div dir="ltr">The design objective is to make thinLTO mostly transparent to binutil tools to enable easy integration with any build system in the wild.  'Pass-through' mode with 'ld -r' instead of the partial LTO mode is another reason.<div><br></div><div>David</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, May 14, 2015 at 7:30 AM, Teresa Johnson <span dir="ltr"><<a href="mailto:tejohnson@google.com" target="_blank">tejohnson@google.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">On Thu, May 14, 2015 at 7:22 AM, Eric Christopher <<a href="mailto:echristo@gmail.com">echristo@gmail.com</a>> wrote:<br>
> So, what Alex is saying is that we have these tools as well and they<br>
> understand bitcode just fine, as well as every object format - not just ELF.<br>
> :)<br>
<br>
</span>Right, there are also LLVM specific versions (llvm-ar, llvm-nm) that<br>
handle bitcode similarly to the way the standard tool + plugin does.<br>
But the goal we are trying to achieve is to allow the standard system<br>
versions of the tools to handle these files without requiring a<br>
plugin. I know the LLVM tool handles other object formats, but I'm not<br>
sure how that helps here? We're not planning to replace those tools,<br>
just allow the standard system versions to handle the intermediate<br>
objects produced by ThinLTO.<br>
<br>
Thanks,<br>
Teresa<br>
<div class="HOEnZb"><div class="h5"><br>
><br>
> -eric<br>
><br>
><br>
> On Thu, May 14, 2015, 6:55 AM Teresa Johnson <<a href="mailto:tejohnson@google.com">tejohnson@google.com</a>> wrote:<br>
>><br>
>> On Wed, May 13, 2015 at 11:23 PM, Xinliang David Li<br>
>> <<a href="mailto:xinliangli@gmail.com">xinliangli@gmail.com</a>> wrote:<br>
>> ><br>
>> ><br>
>> > On Wed, May 13, 2015 at 10:46 PM, Alex Rosenberg <<a href="mailto:alexr@leftfield.org">alexr@leftfield.org</a>><br>
>> > wrote:<br>
>> >><br>
>> >> "ELF-wrapped bitcode" seems potentially controversial to me.<br>
>> >><br>
>> >> What about ar, nm, and various ld implementations adds this<br>
>> >> requirement?<br>
>> >> What about the LLVM implementations of these tools is lacking?<br>
>> ><br>
>> ><br>
>> > Sorry I can not parse your questions properly. Can you make it clearer?<br>
>><br>
>> Alex is asking what the issue is with ar, nm, ld -r and regular<br>
>> bitcode that makes using elf-wrapped bitcode easier.<br>
>><br>
>> The issue is that generally you need to provide a plugin to these<br>
>> tools in order for them to understand and handle bitcode files. We'd<br>
>> like standard tools to work without requiring a plugin as much as<br>
>> possible. And in some cases we want them to be handled different than<br>
>> the way bitcode files are handled with the plugin.<br>
>><br>
>> nm: Without a plugin, normal bitcode files are inscrutable. When<br>
>> provided the gold plugin it can emit the symbols.<br>
>><br>
>> ar: Without a plugin, it will create an archive of bitcode files, but<br>
>> without an index, so it can't be handled by the linker even with a<br>
>> plugin on an -flto link. When ar is provided the gold plugin it does<br>
>> create an index, so the linker + gold plugin handle it appropriately<br>
>> on an -flto link.<br>
>><br>
>> ld -r: Without a plugin, fails when provided bitcode inputs. When<br>
>> provided the gold plugin, it handles them but compiles them all the<br>
>> way through to ELF executable instructions via a partial LTO link.<br>
>> This is where we would like to differ in behavior (while also not<br>
>> requiring a plugin) with ELF-wrapped bitcode: we would like the ld -r<br>
>> output file to still contain ELF-wrapped bitcode, delaying the LTO<br>
>> until the full link step.<br>
>><br>
>> Let me know if that helps address your concerns.<br>
>><br>
>> Thanks,<br>
>> Teresa<br>
>><br>
>> ><br>
>> > David<br>
>> ><br>
>> >><br>
>> >><br>
>> >> Alex<br>
>> >><br>
>> >> > On May 13, 2015, at 7:44 PM, Teresa Johnson <<a href="mailto:tejohnson@google.com">tejohnson@google.com</a>><br>
>> >> > wrote:<br>
>> >> ><br>
>> >> > I've included below an RFC for implementing ThinLTO in LLVM, looking<br>
>> >> > forward to feedback and questions.<br>
>> >> > Thanks!<br>
>> >> > Teresa<br>
>> >> ><br>
>> >> ><br>
>> >> ><br>
>> >> > RFC to discuss plans for implementing ThinLTO upstream. Background<br>
>> >> > can<br>
>> >> > be found in slides from EuroLLVM 2015:<br>
>> >> ><br>
>> >> ><br>
>> >> > <a href="https://drive.google.com/open?id=0B036uwnWM6RWWER1ZEl5SUNENjQ&authuser=0" target="_blank">https://drive.google.com/open?id=0B036uwnWM6RWWER1ZEl5SUNENjQ&authuser=0</a>)<br>
>> >> > As described in the talk, we have a prototype implementation, and<br>
>> >> > would like to start staging patches upstream. This RFC describes a<br>
>> >> > breakdown of the major pieces. We would like to commit upstream<br>
>> >> > gradually in several stages, with all functionality off by default.<br>
>> >> > The core ThinLTO importing support and tuning will require frequent<br>
>> >> > change and iteration during testing and tuning, and for that part we<br>
>> >> > would like to commit rapidly (off by default). See the proposed<br>
>> >> > staged<br>
>> >> > implementation described in the Implementation Plan section.<br>
>> >> ><br>
>> >> ><br>
>> >> > ThinLTO Overview<br>
>> >> > ==============<br>
>> >> ><br>
>> >> > See the talk slides linked above for more details. The following is a<br>
>> >> > high-level overview of the motivation.<br>
>> >> ><br>
>> >> > Cross Module Optimization (CMO) is an effective means for improving<br>
>> >> > runtime performance, by extending the scope of optimizations across<br>
>> >> > source module boundaries. Without CMO, the compiler is limited to<br>
>> >> > optimizing within the scope of single source modules. Two solutions<br>
>> >> > for enabling CMO are Link-Time Optimization (LTO), which is currently<br>
>> >> > supported in LLVM and GCC, and Lightweight-Interprocedural<br>
>> >> > Optimization (LIPO). However, each of these solutions has limitations<br>
>> >> > that prevent it from being enabled by default. ThinLTO is a new<br>
>> >> > approach that attempts to address these limitations, with a goal of<br>
>> >> > being enabled more broadly. ThinLTO is designed with many of the same<br>
>> >> > principals as LIPO, and therefore its advantages, without any of its<br>
>> >> > inherent weakness. Unlike in LIPO where the module group decision is<br>
>> >> > made at profile training runtime, ThinLTO makes the decision at<br>
>> >> > compile time, but in a lazy mode that facilitates large scale<br>
>> >> > parallelism. The serial linker plugin phase is designed to be razor<br>
>> >> > thin and blazingly fast. By default this step only does minimal<br>
>> >> > preparation work to enable the parallel lazy importing performed<br>
>> >> > later. ThinLTO aims to be scalable like a regular O2 build, enabling<br>
>> >> > CMO on machines without large memory configurations, while also<br>
>> >> > integrating well with distributed build systems. Results from early<br>
>> >> > prototyping on SPEC cpu2006 C++ benchmarks are in line with<br>
>> >> > expectations that ThinLTO can scale like O2 while enabling much of<br>
>> >> > the<br>
>> >> > CMO performed during a full LTO build.<br>
>> >> ><br>
>> >> ><br>
>> >> > A ThinLTO build is divided into 3 phases, which are referred to in<br>
>> >> > the<br>
>> >> > following implementation plan:<br>
>> >> ><br>
>> >> > phase-1: IR and Function Summary Generation (-c compile)<br>
>> >> > phase-2: Thin Linker Plugin Layer (thin archive linker step)<br>
>> >> > phase-3: Parallel Backend with Demand-Driven Importing<br>
>> >> ><br>
>> >> ><br>
>> >> > Implementation Plan<br>
>> >> > ================<br>
>> >> ><br>
>> >> > This section gives a high-level breakdown of the ThinLTO support that<br>
>> >> > will be added, in roughly the order that the patches would be staged.<br>
>> >> > The patches are divided into three stages. The first stage contains a<br>
>> >> > minimal amount of preparation work that is not ThinLTO-specific. The<br>
>> >> > second stage contains most of the infrastructure for ThinLTO, which<br>
>> >> > will be off by default. The third stage includes<br>
>> >> > enhancements/improvements/tunings that can be performed after the<br>
>> >> > main<br>
>> >> > ThinLTO infrastructure is in.<br>
>> >> ><br>
>> >> > The second and third implementation stages will initially be very<br>
>> >> > volatile, requiring a lot of iterations and tuning with large apps to<br>
>> >> > get stabilized. Therefore it will be important to do fast commits for<br>
>> >> > these implementation stages.<br>
>> >> ><br>
>> >> ><br>
>> >> > 1. Stage 1: Preparation<br>
>> >> > -------------------------------<br>
>> >> ><br>
>> >> > The first planned sets of patches are enablers for ThinLTO work:<br>
>> >> ><br>
>> >> ><br>
>> >> > a. LTO directory structure:<br>
>> >> ><br>
>> >> > Restructure the LTO directory to remove circular dependence when<br>
>> >> > ThinLTO pass added. Because ThinLTO is being implemented as a SCC<br>
>> >> > pass<br>
>> >> > within Transforms/IPO, and leverages the LTOModule class for linking<br>
>> >> > in functions from modules, IPO then requires the LTO library. This<br>
>> >> > creates a circular dependence between LTO and IPO. To break that, we<br>
>> >> > need to split the lib/LTO directory/library into lib/LTO/CodeGen and<br>
>> >> > lib/LTO/Module, containing LTOCodeGenerator and LTOModule,<br>
>> >> > respectively. Only LTOCodeGenerator has a dependence on IPO, removing<br>
>> >> > the circular dependence.<br>
>> >> ><br>
>> >> ><br>
>> >> > b. ELF wrapper generation support:<br>
>> >> ><br>
>> >> > Implement ELF wrapped bitcode writer. In order to more easily<br>
>> >> > interact<br>
>> >> > with tools such as $AR, $NM, and “$LD -r” we plan to emit the phase-1<br>
>> >> > bitcode wrapped in ELF via the .llvmbc section, along with a symbol<br>
>> >> > table. The goal is both to interact with these tools without<br>
>> >> > requiring<br>
>> >> > a plugin, and also to avoid doing partial LTO/ThinLTO across files<br>
>> >> > linked with “$LD -r” (i.e. the resulting object file should still<br>
>> >> > contain ELF-wrapped bitcode to enable ThinLTO at the full link step).<br>
>> >> > I will send a separate design document for these changes, but the<br>
>> >> > following is a high-level overview.<br>
>> >> ><br>
>> >> > Support was added to LLVM for reading ELF-wrapped bitcode<br>
>> >> > (<a href="http://reviews.llvm.org/rL218078" target="_blank">http://reviews.llvm.org/rL218078</a>), but there does not yet exist<br>
>> >> > support in LLVM/Clang for emitting bitcode wrapped in ELF. I plan to<br>
>> >> > add support for optionally generating bitcode in an ELF file<br>
>> >> > containing a single .llvmbc section holding the bitcode.<br>
>> >> > Specifically,<br>
>> >> > the patch would add new options “emit-llvm-bc-elf” (object file) and<br>
>> >> > corresponding “emit-llvm-elf” (textual assembly code equivalent).<br>
>> >> > Eventually these would be automatically triggered under “-fthinlto<br>
>> >> > -c”<br>
>> >> > and “-fthinlto -S”, respectively.<br>
>> >> ><br>
>> >> > Additionally, a symbol table will be generated in the ELF file,<br>
>> >> > holding the function symbols within the bitcode. This facilitates<br>
>> >> > handling archives of the ELF-wrapped bitcode created with $AR, since<br>
>> >> > the archive will have a symbol table as well. The archive symbol<br>
>> >> > table<br>
>> >> > enables gold to extract and pass to the plugin the constituent<br>
>> >> > ELF-wrapped bitcode files. To support the concatenated llvmbc section<br>
>> >> > generated by “$LD -r”, some handling needs to be added to gold and to<br>
>> >> > the backend driver to process each original module’s bitcode.<br>
>> >> ><br>
>> >> > The function index/summary will later be added as a special ELF<br>
>> >> > section alongside the .llvmbc sections.<br>
>> >> ><br>
>> >> ><br>
>> >> > 2. Stage 2: ThinLTO Infrastructure<br>
>> >> > ----------------------------------------------<br>
>> >> ><br>
>> >> > The next set of patches adds the base implementation of the ThinLTO<br>
>> >> > infrastructure, specifically those required to make ThinLTO<br>
>> >> > functional<br>
>> >> > and generate correct but not necessarily high-performing binaries. It<br>
>> >> > also does not include support to make debug support under -g<br>
>> >> > efficient<br>
>> >> > with ThinLTO.<br>
>> >> ><br>
>> >> ><br>
>> >> > a. Clang/LLVM/gold linker options:<br>
>> >> ><br>
>> >> > An early set of clang/llvm patches is needed to provide options to<br>
>> >> > enable ThinLTO (off by default), so that the rest of the<br>
>> >> > implementation can be disabled by default as it is added.<br>
>> >> > Specifically, clang options -fthinlto (used instead of -flto) will<br>
>> >> > cause clang to invoke the phase-1 emission of LLVM bitcode and<br>
>> >> > function summary/index on a compile step, and pass the appropriate<br>
>> >> > option to the gold plugin on a link step. The -thinlto option will be<br>
>> >> > added to the gold plugin and llvm-lto tool to launch the phase-2 thin<br>
>> >> > archive step. The -thinlto option will also be added to the ‘opt’<br>
>> >> > tool<br>
>> >> > to invoke it as a phase-3 parallel backend instance.<br>
>> >> ><br>
>> >> ><br>
>> >> > b. Thin-archive linking support in Gold plugin and llvm-lto:<br>
>> >> ><br>
>> >> > Under the new plugin option (see above), the plugin needs to perform<br>
>> >> > the phase-2 (thin archive) link which simply emits a combined<br>
>> >> > function<br>
>> >> > map from the linked modules, without actually performing the normal<br>
>> >> > link. Corresponding support should be added to the standalone<br>
>> >> > llvm-lto<br>
>> >> > tool to enable testing/debugging without involving the linker and<br>
>> >> > plugin.<br>
>> >> ><br>
>> >> ><br>
>> >> > c. ThinLTO backend support:<br>
>> >> ><br>
>> >> > Support for invoking a phase-3 backend invocation (including<br>
>> >> > importing) on a module should be added to the ‘opt’ tool under the<br>
>> >> > new<br>
>> >> > option. The main change under the option is to instantiate a Linker<br>
>> >> > object used to manage the process of linking imported functions into<br>
>> >> > the module, efficient read of the combined function map, and enable<br>
>> >> > the ThinLTO import pass.<br>
>> >> ><br>
>> >> ><br>
>> >> > d. Function index/summary support:<br>
>> >> ><br>
>> >> > This includes infrastructure for writing and reading the function<br>
>> >> > index/summary section. As noted earlier this will be encoded in a<br>
>> >> > special ELF section within the module, alongside the .llvmbc section<br>
>> >> > containing the bitcode. The thin archive generated by phase-2 of<br>
>> >> > ThinLTO simply contains all of the function index/summary sections<br>
>> >> > across the linked modules, organized for efficient function lookup.<br>
>> >> ><br>
>> >> > Each function available for importing from the module contains an<br>
>> >> > entry in the module’s function index/summary section and in the<br>
>> >> > resulting combined function map. Each function entry contains that<br>
>> >> > function’s offset within the bitcode file, used to efficiently locate<br>
>> >> > and quickly import just that function. The entry also contains<br>
>> >> > summary<br>
>> >> > information (e.g. basic information determined during parsing such as<br>
>> >> > the number of instructions in the function), that will be used to<br>
>> >> > help<br>
>> >> > guide later import decisions. Because the contents of this section<br>
>> >> > will change frequently during ThinLTO tuning, it should also be<br>
>> >> > marked<br>
>> >> > with a version id for backwards compatibility or version checking.<br>
>> >> ><br>
>> >> ><br>
>> >> > e. ThinLTO importing support:<br>
>> >> ><br>
>> >> > Support for the mechanics of importing functions from other modules,<br>
>> >> > which can go in gradually as a set of patches since it will be off by<br>
>> >> > default. Separate patches can include:<br>
>> >> ><br>
>> >> > - BitcodeReader changes to use function index to import/deserialize<br>
>> >> > single function of interest (small changes, leverages existing lazy<br>
>> >> > streamer support).<br>
>> >> ><br>
>> >> > - Minor LTOModule changes to pass the ThinLTO function to import and<br>
>> >> > its index into bitcode reader.<br>
>> >> ><br>
>> >> > - Marking of imported functions (for use in ThinLTO-specific symbol<br>
>> >> > linking and global DCE, for example). This can be in-memory<br>
>> >> > initially,<br>
>> >> > but IR support may be required in order to support streaming bitcode<br>
>> >> > out and back in again after importing.<br>
>> >> ><br>
>> >> > - ModuleLinker changes to do ThinLTO-specific symbol linking and<br>
>> >> > static promotion when necessary. The linkage type of imported<br>
>> >> > functions changes to AvailableExternallyLinkage, for example. Statics<br>
>> >> > must be promoted in certain cases, and renamed in consistent ways.<br>
>> >> ><br>
>> >> > - GlobalDCE changes to support removing imported functions that were<br>
>> >> > not inlined (very small changes to existing pass logic).<br>
>> >> ><br>
>> >> ><br>
>> >> > f. ThinLTO Import Driver SCC pass:<br>
>> >> ><br>
>> >> > Adds Transforms/IPO/ThinLTO.cpp with framework for doing ThinLTO via<br>
>> >> > an SCC pass, enabled only under -fthinlto options. The pass includes<br>
>> >> > utilizing the thin archive (global function index/summary), import<br>
>> >> > decision heuristics, invocation of LTOModule/ModuleLinker routines<br>
>> >> > that perform the import, and any necessary callgraph updates and<br>
>> >> > verification.<br>
>> >> ><br>
>> >> ><br>
>> >> > g. Backend Driver:<br>
>> >> ><br>
>> >> > For a single node build, the gold plugin can simply write a makefile<br>
>> >> > and fork the parallel backend instances directly via parallel make.<br>
>> >> ><br>
>> >> ><br>
>> >> > 3. Stage 3: ThinLTO Tuning and Enhancements<br>
>> >> > ----------------------------------------------------------------<br>
>> >> ><br>
>> >> > This refers to the patches that are not required for ThinLTO to work,<br>
>> >> > but rather to improve compile time, memory, run-time performance and<br>
>> >> > usability.<br>
>> >> ><br>
>> >> ><br>
>> >> > a. Lazy Debug Metadata Linking:<br>
>> >> ><br>
>> >> > The prototype implementation included lazy importing of module-level<br>
>> >> > metadata during the ThinLTO pass finalization (i.e. after all<br>
>> >> > function<br>
>> >> > importing is complete). This actually applies to all module-level<br>
>> >> > metadata, not just debug, although it is the largest. This can be<br>
>> >> > added as a separate set of patches. Changes to BitcodeReader,<br>
>> >> > ValueMapper, ModuleLinker<br>
>> >> ><br>
>> >> ><br>
>> >> > b. Import Tuning:<br>
>> >> ><br>
>> >> > Tuning the import strategy will be an iterative process that will<br>
>> >> > continue to be refined over time. It involves several different types<br>
>> >> > of changes: adding support for recording additional metrics in the<br>
>> >> > function summary, such as profile data and optional heavier-weight<br>
>> >> > IPA<br>
>> >> > analyses, and tuning the import heuristics based on the summary and<br>
>> >> > callsite context.<br>
>> >> ><br>
>> >> ><br>
>> >> > c. Combined Function Map Pruning:<br>
>> >> ><br>
>> >> > The combined function map can be pruned of functions that are<br>
>> >> > unlikely<br>
>> >> > to benefit from being imported. For example, during the phase-2 thin<br>
>> >> > archive plug step we can safely omit large and (with profile data)<br>
>> >> > cold functions, which are unlikely to benefit from being inlined.<br>
>> >> > Additionally, all but one copy of comdat functions can be suppressed.<br>
>> >> ><br>
>> >> ><br>
>> >> > d. Distributed Build System Integration:<br>
>> >> ><br>
>> >> > For a distributed build system, the gold plugin should write the<br>
>> >> > parallel backend invocations into a makefile, including the mapping<br>
>> >> > from the IR file to the real object file path, and exit. Additional<br>
>> >> > work needs to be done in the distributed build system itself to<br>
>> >> > distribute and dispatch the parallel backend jobs to the build<br>
>> >> > cluster.<br>
>> >> ><br>
>> >> ><br>
>> >> > e. Dependence Tracking and Incremental Compiles:<br>
>> >> ><br>
>> >> > In order to support build systems that stage from local disks or<br>
>> >> > network storage, the plugin will optionally support computation of<br>
>> >> > dependent sets of IR files that each module may import from. This can<br>
>> >> > be computed from profile data, if it exists, or from the symbol table<br>
>> >> > and heuristics if not. These dependence sets also enable support for<br>
>> >> > incremental backend compiles.<br>
>> >> ><br>
>> >> ><br>
>> >> ><br>
>> >> > --<br>
>> >> > Teresa Johnson | Software Engineer | <a href="mailto:tejohnson@google.com">tejohnson@google.com</a> |<br>
>> >> > <a href="tel:408-460-2413" value="+14084602413">408-460-2413</a><br>
>> >> ><br>
>> >> > _______________________________________________<br>
>> >> > LLVM Developers mailing list<br>
>> >> > <a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a>         <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
>> >> > <a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
>> >><br>
>> >> _______________________________________________<br>
>> >> LLVM Developers mailing list<br>
>> >> <a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a>         <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
>> >> <a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
>> ><br>
>> ><br>
>><br>
>><br>
>><br>
>> --<br>
>> Teresa Johnson | Software Engineer | <a href="mailto:tejohnson@google.com">tejohnson@google.com</a> | <a href="tel:408-460-2413" value="+14084602413">408-460-2413</a><br>
>><br>
>> _______________________________________________<br>
>> LLVM Developers mailing list<br>
>> <a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a>         <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
>> <a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
<br>
<br>
<br>
--<br>
Teresa Johnson | Software Engineer | <a href="mailto:tejohnson@google.com">tejohnson@google.com</a> | <a href="tel:408-460-2413" value="+14084602413">408-460-2413</a><br>
</div></div></blockquote></div><br></div>