[LLVMdev] RFC: ThinLTO Impementation Plan

[Nick Lewycky]

On 13 May 2015 at 11:44, Teresa Johnson <tejohnson at google.com> wrote:

> I've included below an RFC for implementing ThinLTO in LLVM, looking
> forward to feedback and questions.
>

Thanks! I have to admit up front that I haven't read through the whole
thread, but I have a couple comments. Overall this looks like a really nice
design and unusually thorough RFC!

Thanks!
> Teresa
>
>
>
> RFC to discuss plans for implementing ThinLTO upstream. Background can
> be found in slides from EuroLLVM 2015:
>
> https://drive.google.com/open?id=0B036uwnWM6RWWER1ZEl5SUNENjQ&authuser=0)
> As described in the talk, we have a prototype implementation, and
> would like to start staging patches upstream. This RFC describes a
> breakdown of the major pieces. We would like to commit upstream
> gradually in several stages, with all functionality off by default.
> The core ThinLTO importing support and tuning will require frequent
> change and iteration during testing and tuning, and for that part we
> would like to commit rapidly (off by default). See the proposed staged
> implementation described in the Implementation Plan section.
>
>
> ThinLTO Overview
> ==============
>
> See the talk slides linked above for more details. The following is a
> high-level overview of the motivation.
>
> Cross Module Optimization (CMO) is an effective means for improving
> runtime performance, by extending the scope of optimizations across
> source module boundaries. Without CMO, the compiler is limited to
> optimizing within the scope of single source modules. Two solutions
> for enabling CMO are Link-Time Optimization (LTO), which is currently
> supported in LLVM and GCC, and Lightweight-Interprocedural
> Optimization (LIPO). However, each of these solutions has limitations
> that prevent it from being enabled by default. ThinLTO is a new
> approach that attempts to address these limitations, with a goal of
> being enabled more broadly. ThinLTO is designed with many of the same
> principals as LIPO, and therefore its advantages, without any of its
> inherent weakness. Unlike in LIPO where the module group decision is
> made at profile training runtime, ThinLTO makes the decision at
> compile time, but in a lazy mode that facilitates large scale
> parallelism. The serial linker plugin phase is designed to be razor
> thin and blazingly fast. By default this step only does minimal
> preparation work to enable the parallel lazy importing performed
> later. ThinLTO aims to be scalable like a regular O2 build, enabling
> CMO on machines without large memory configurations, while also
> integrating well with distributed build systems. Results from early
> prototyping on SPEC cpu2006 C++ benchmarks are in line with
> expectations that ThinLTO can scale like O2 while enabling much of the
> CMO performed during a full LTO build.
>

This is different from llvm's current LTO approach ("big bang LTO", where
we combine all TUs into a single big Module and the optimize and codegen
it). It sounds like there's two goals here, multi-machine parallelism and
reducing memory usage (by splitting the Module out to multiple machines)
and most of the interesting logic goes into deciding where to split a
Module.

I think ThinLTO was designed under the assumption that we would not be able
to fit a large program into memory on a single machine (or that even if we
could, we wouldn't be able to compile quickly enough by employing
multi-core parallelism). This is in contrast to previously considered
approaches of improving big bang LTO to handle very large programs through
changes to the IR, in-memory representation, on-disk representation and
threading. Starting with the assumption that we will need multiple
machines, ThinLTO looks like an excellent design. I just wanted to call out
that design requirement and how it's different from how llvm has thought
about LTO in the past.

A ThinLTO build is divided into 3 phases, which are referred to in the
> following implementation plan:
>
> phase-1: IR and Function Summary Generation (-c compile)
> phase-2: Thin Linker Plugin Layer (thin archive linker step)
> phase-3: Parallel Backend with Demand-Driven Importing
>
>
> Implementation Plan
> ================
>
> This section gives a high-level breakdown of the ThinLTO support that
> will be added, in roughly the order that the patches would be staged.
> The patches are divided into three stages. The first stage contains a
> minimal amount of preparation work that is not ThinLTO-specific. The
> second stage contains most of the infrastructure for ThinLTO, which
> will be off by default. The third stage includes
> enhancements/improvements/tunings that can be performed after the main
> ThinLTO infrastructure is in.
>
> The second and third implementation stages will initially be very
> volatile, requiring a lot of iterations and tuning with large apps to
> get stabilized. Therefore it will be important to do fast commits for
> these implementation stages.
>
>
> 1. Stage 1: Preparation
> -------------------------------
>
> The first planned sets of patches are enablers for ThinLTO work:
>
>
> a. LTO directory structure:
>
> Restructure the LTO directory to remove circular dependence when
> ThinLTO pass added. Because ThinLTO is being implemented as a SCC pass
> within Transforms/IPO, and leverages the LTOModule class for linking
> in functions from modules, IPO then requires the LTO library. This
> creates a circular dependence between LTO and IPO. To break that, we
> need to split the lib/LTO directory/library into lib/LTO/CodeGen and
> lib/LTO/Module, containing LTOCodeGenerator and LTOModule,
> respectively. Only LTOCodeGenerator has a dependence on IPO, removing
> the circular dependence.
>
>
> b. ELF wrapper generation support:
>
> Implement ELF wrapped bitcode writer. In order to more easily interact
> with tools such as $AR, $NM, and “$LD -r” we plan to emit the phase-1
> bitcode wrapped in ELF via the .llvmbc section, along with a symbol
> table. The goal is both to interact with these tools without requiring
> a plugin, and also to avoid doing partial LTO/ThinLTO across files
> linked with “$LD -r” (i.e. the resulting object file should still
> contain ELF-wrapped bitcode to enable ThinLTO at the full link step).
> I will send a separate design document for these changes, but the
> following is a high-level overview.
>
> Support was added to LLVM for reading ELF-wrapped bitcode
> (http://reviews.llvm.org/rL218078), but there does not yet exist
> support in LLVM/Clang for emitting bitcode wrapped in ELF. I plan to
> add support for optionally generating bitcode in an ELF file
> containing a single .llvmbc section holding the bitcode. Specifically,
> the patch would add new options “emit-llvm-bc-elf” (object file) and
> corresponding “emit-llvm-elf” (textual assembly code equivalent).
> Eventually these would be automatically triggered under “-fthinlto -c”
> and “-fthinlto -S”, respectively.
>
> Additionally, a symbol table will be generated in the ELF file,
> holding the function symbols within the bitcode. This facilitates
> handling archives of the ELF-wrapped bitcode created with $AR, since
> the archive will have a symbol table as well. The archive symbol table
> enables gold to extract and pass to the plugin the constituent
> ELF-wrapped bitcode files. To support the concatenated llvmbc section
> generated by “$LD -r”, some handling needs to be added to gold and to
> the backend driver to process each original module’s bitcode.
>
> The function index/summary will later be added as a special ELF
> section alongside the .llvmbc sections.
>

We've historically pushed back on adding ELF because it doesn't add any new
information that isn't present in the .bc file, and we care a lot about
minimizing I/O time (I recall an encoding change in the bitcode format
shrinking .bc files 10% which led to a big improvement in LTO times for
Darwin).

There's a few practical matters about what needs to be in this ELF symbol
table; what about symbols that we reference, instead of just those we
define? what about the sizes of symbols we define? what about the case
where llvm codegen ends up defining (or referencing) a function that isn't
mentioned in the IR (a common example is emitting a call to memcpy for
argument lowering)? If you have a set of tools in mind, we can make the ELF
accurate enough to work with those tools, but it's not clear to me how to
make it work for fully general ELF-expecting programs without doing full
codegen into the file (IIRC, this is what GCC does). Are 'ar', 'nm' and
'ld' the only programs?

Finally, suppose you get into a situation where you implement ThinLTO with
the elf wrappers and then examine the compile time, memory usage, file size
and I/O, and find that ThinLTO isn't performing as well as we like. The
next question is going to be "well, what if we removed that extra I/O time,
file size (copying time) and memory usage from having that ELF wrapper"?
That's why I think of a .bc-only version as being the ideal version, and
that having ELF wrapping is a good idea for supporting legacy programs as
needed.

2. Stage 2: ThinLTO Infrastructure
> ----------------------------------------------
>
> The next set of patches adds the base implementation of the ThinLTO
> infrastructure, specifically those required to make ThinLTO functional
> and generate correct but not necessarily high-performing binaries. It
> also does not include support to make debug support under -g efficient
> with ThinLTO.
>
>
> a. Clang/LLVM/gold linker options:
>
> An early set of clang/llvm patches is needed to provide options to
> enable ThinLTO (off by default), so that the rest of the
> implementation can be disabled by default as it is added.
> Specifically, clang options -fthinlto (used instead of -flto) will
> cause clang to invoke the phase-1 emission of LLVM bitcode and
> function summary/index on a compile step, and pass the appropriate
> option to the gold plugin on a link step. The -thinlto option will be
> added to the gold plugin and llvm-lto tool to launch the phase-2 thin
> archive step. The -thinlto option will also be added to the ‘opt’ tool
> to invoke it as a phase-3 parallel backend instance.
>
>
> b. Thin-archive linking support in Gold plugin and llvm-lto:
>
> Under the new plugin option (see above), the plugin needs to perform
> the phase-2 (thin archive) link which simply emits a combined function
> map from the linked modules, without actually performing the normal
> link. Corresponding support should be added to the standalone llvm-lto
> tool to enable testing/debugging without involving the linker and
> plugin.
>
>
> c. ThinLTO backend support:
>
> Support for invoking a phase-3 backend invocation (including
> importing) on a module should be added to the ‘opt’ tool under the new
> option. The main change under the option is to instantiate a Linker
> object used to manage the process of linking imported functions into
> the module, efficient read of the combined function map, and enable
> the ThinLTO import pass.
>
>
> d. Function index/summary support:
>
> This includes infrastructure for writing and reading the function
> index/summary section. As noted earlier this will be encoded in a
> special ELF section within the module, alongside the .llvmbc section
> containing the bitcode. The thin archive generated by phase-2 of
> ThinLTO simply contains all of the function index/summary sections
> across the linked modules, organized for efficient function lookup.
>
> Each function available for importing from the module contains an
> entry in the module’s function index/summary section and in the
> resulting combined function map. Each function entry contains that
> function’s offset within the bitcode file, used to efficiently locate
> and quickly import just that function. The entry also contains summary
> information (e.g. basic information determined during parsing such as
> the number of instructions in the function), that will be used to help
> guide later import decisions. Because the contents of this section
> will change frequently during ThinLTO tuning, it should also be marked
> with a version id for backwards compatibility or version checking.
>

I have an idea for a future version.

Give passes the ability to write their own summary data at compile time,
and to read them in the backends. Merge these summaries in the link, then
after splitting send the merged summaries to each backend regardless of
whether it imports the function body. For instance, dead argument
elimination could summarize which functions ignore which arguments (either
entirely, or locally except for which arguments in which callees).
Receiving a full graph of this is smaller than the full implementations of
the functions, and yet would allow each backend to do an analysis of the
full graph. Function A's body is in this backend, and A calls B whose body
is not available to this backend. The summary would include that the first
argument to B is dead, so we can optimize away the chain of computation
leading to it in A. (I think a more compelling example will be alias
analysis, but it would make for a messier example.)

Nick

e. ThinLTO importing support:
>
> Support for the mechanics of importing functions from other modules,
> which can go in gradually as a set of patches since it will be off by
> default. Separate patches can include:
>
> - BitcodeReader changes to use function index to import/deserialize
> single function of interest (small changes, leverages existing lazy
> streamer support).
>
> - Minor LTOModule changes to pass the ThinLTO function to import and
> its index into bitcode reader.
>
> - Marking of imported functions (for use in ThinLTO-specific symbol
> linking and global DCE, for example). This can be in-memory initially,
> but IR support may be required in order to support streaming bitcode
> out and back in again after importing.
>
> - ModuleLinker changes to do ThinLTO-specific symbol linking and
> static promotion when necessary. The linkage type of imported
> functions changes to AvailableExternallyLinkage, for example. Statics
> must be promoted in certain cases, and renamed in consistent ways.
>
> - GlobalDCE changes to support removing imported functions that were
> not inlined (very small changes to existing pass logic).
>
>
> f. ThinLTO Import Driver SCC pass:
>
> Adds Transforms/IPO/ThinLTO.cpp with framework for doing ThinLTO via
> an SCC pass, enabled only under -fthinlto options. The pass includes
> utilizing the thin archive (global function index/summary), import
> decision heuristics, invocation of LTOModule/ModuleLinker routines
> that perform the import, and any necessary callgraph updates and
> verification.
>
>
> g. Backend Driver:
>
> For a single node build, the gold plugin can simply write a makefile
> and fork the parallel backend instances directly via parallel make.
>
>
> 3. Stage 3: ThinLTO Tuning and Enhancements
> ----------------------------------------------------------------
>
> This refers to the patches that are not required for ThinLTO to work,
> but rather to improve compile time, memory, run-time performance and
> usability.
>
>
> a. Lazy Debug Metadata Linking:
>
> The prototype implementation included lazy importing of module-level
> metadata during the ThinLTO pass finalization (i.e. after all function
> importing is complete). This actually applies to all module-level
> metadata, not just debug, although it is the largest. This can be
> added as a separate set of patches. Changes to BitcodeReader,
> ValueMapper, ModuleLinker
>
>
> b. Import Tuning:
>
> Tuning the import strategy will be an iterative process that will
> continue to be refined over time. It involves several different types
> of changes: adding support for recording additional metrics in the
> function summary, such as profile data and optional heavier-weight IPA
> analyses, and tuning the import heuristics based on the summary and
> callsite context.
>
>
> c. Combined Function Map Pruning:
>
> The combined function map can be pruned of functions that are unlikely
> to benefit from being imported. For example, during the phase-2 thin
> archive plug step we can safely omit large and (with profile data)
> cold functions, which are unlikely to benefit from being inlined.
> Additionally, all but one copy of comdat functions can be suppressed.
>
>
> d. Distributed Build System Integration:
>
> For a distributed build system, the gold plugin should write the
> parallel backend invocations into a makefile, including the mapping
> from the IR file to the real object file path, and exit. Additional
> work needs to be done in the distributed build system itself to
> distribute and dispatch the parallel backend jobs to the build
> cluster.
>
>
> e. Dependence Tracking and Incremental Compiles:
>
> In order to support build systems that stage from local disks or
> network storage, the plugin will optionally support computation of
> dependent sets of IR files that each module may import from. This can
> be computed from profile data, if it exists, or from the symbol table
> and heuristics if not. These dependence sets also enable support for
> incremental backend compiles.
>
>
>
> --
> Teresa Johnson | Software Engineer | tejohnson at google.com | 408-460-2413
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150519/4a60a5b9/attachment.html>