| ====================================================== | |
| LLVM Link Time Optimization: Design and Implementation | |
| ====================================================== | |
| .. contents:: | |
| :local: | |
| Description | |
| =========== | |
| LLVM features powerful intermodular optimizations which can be used at link | |
| time. Link Time Optimization (LTO) is another name for intermodular | |
| optimization when performed during the link stage. This document describes the | |
| interface and design between the LTO optimizer and the linker. | |
| Design Philosophy | |
| ================= | |
| The LLVM Link Time Optimizer provides complete transparency, while doing | |
| intermodular optimization, in the compiler tool chain. Its main goal is to let | |
| the developer take advantage of intermodular optimizations without making any | |
| significant changes to the developer's makefiles or build system. This is | |
| achieved through tight integration with the linker. In this model, the linker | |
| treats LLVM bitcode files like native object files and allows mixing and | |
| matching among them. The linker uses `libLTO`_, a shared object, to handle LLVM | |
| bitcode files. This tight integration between the linker and LLVM optimizer | |
| helps to do optimizations that are not possible in other models. The linker | |
| input allows the optimizer to avoid relying on conservative escape analysis. | |
| .. _libLTO-example: | |
| Example of link time optimization | |
| --------------------------------- | |
| The following example illustrates the advantages of LTO's integrated approach | |
| and clean interface. This example requires a system linker which supports LTO | |
| through the interface described in this document. Here, clang transparently | |
| invokes system linker. | |
| * Input source file ``a.c`` is compiled into LLVM bitcode form. | |
| * Input source file ``main.c`` is compiled into native object code. | |
| .. code-block:: c++ | |
| --- a.h --- | |
| extern int foo1(void); | |
| extern void foo2(void); | |
| extern void foo4(void); | |
| --- a.c --- | |
| #include "a.h" | |
| static signed int i = 0; | |
| void foo2(void) { | |
| i = -1; | |
| } | |
| static int foo3() { | |
| foo4(); | |
| return 10; | |
| } | |
| int foo1(void) { | |
| int data = 0; | |
| if (i < 0) | |
| data = foo3(); | |
| data = data + 42; | |
| return data; | |
| } | |
| --- main.c --- | |
| #include <stdio.h> | |
| #include "a.h" | |
| void foo4(void) { | |
| printf("Hi\n"); | |
| } | |
| int main() { | |
| return foo1(); | |
| } | |
| To compile, run: | |
| .. code-block:: console | |
| % clang -flto -c a.c -o a.o # <-- a.o is LLVM bitcode file | |
| % clang -c main.c -o main.o # <-- main.o is native object file | |
| % clang -flto a.o main.o -o main # <-- standard link command with -flto | |
| * In this example, the linker recognizes that ``foo2()`` is an externally | |
| visible symbol defined in LLVM bitcode file. The linker completes its usual | |
| symbol resolution pass and finds that ``foo2()`` is not used | |
| anywhere. This information is used by the LLVM optimizer and it | |
| removes ``foo2()``. | |
| * As soon as ``foo2()`` is removed, the optimizer recognizes that condition ``i | |
| < 0`` is always false, which means ``foo3()`` is never used. Hence, the | |
| optimizer also removes ``foo3()``. | |
| * And this in turn, enables linker to remove ``foo4()``. | |
| This example illustrates the advantage of tight integration with the | |
| linker. Here, the optimizer can not remove ``foo3()`` without the linker's | |
| input. | |
| Alternative Approaches | |
| ---------------------- | |
| **Compiler driver invokes link time optimizer separately.** | |
| In this model the link time optimizer is not able to take advantage of | |
| information collected during the linker's normal symbol resolution phase. | |
| In the above example, the optimizer can not remove ``foo2()`` without the | |
| linker's input because it is externally visible. This in turn prohibits the | |
| optimizer from removing ``foo3()``. | |
| **Use separate tool to collect symbol information from all object files.** | |
| In this model, a new, separate, tool or library replicates the linker's | |
| capability to collect information for link time optimization. Not only is | |
| this code duplication difficult to justify, but it also has several other | |
| disadvantages. For example, the linking semantics and the features provided | |
| by the linker on various platform are not unique. This means, this new tool | |
| needs to support all such features and platforms in one super tool or a | |
| separate tool per platform is required. This increases maintenance cost for | |
| link time optimizer significantly, which is not necessary. This approach | |
| also requires staying synchronized with linker developments on various | |
| platforms, which is not the main focus of the link time optimizer. Finally, | |
| this approach increases end user's build time due to the duplication of work | |
| done by this separate tool and the linker itself. | |
| Multi-phase communication between ``libLTO`` and linker | |
| ======================================================= | |
| The linker collects information about symbol definitions and uses in various | |
| link objects which is more accurate than any information collected by other | |
| tools during typical build cycles. The linker collects this information by | |
| looking at the definitions and uses of symbols in native .o files and using | |
| symbol visibility information. The linker also uses user-supplied information, | |
| such as a list of exported symbols. LLVM optimizer collects control flow | |
| information, data flow information and knows much more about program structure | |
| from the optimizer's point of view. Our goal is to take advantage of tight | |
| integration between the linker and the optimizer by sharing this information | |
| during various linking phases. | |
| Phase 1 : Read LLVM Bitcode Files | |
| --------------------------------- | |
| The linker first reads all object files in natural order and collects symbol | |
| information. This includes native object files as well as LLVM bitcode files. | |
| To minimize the cost to the linker in the case that all .o files are native | |
| object files, the linker only calls ``lto_module_create()`` when a supplied | |
| object file is found to not be a native object file. If ``lto_module_create()`` | |
| returns that the file is an LLVM bitcode file, the linker then iterates over the | |
| module using ``lto_module_get_symbol_name()`` and | |
| ``lto_module_get_symbol_attribute()`` to get all symbols defined and referenced. | |
| This information is added to the linker's global symbol table. | |
| The lto* functions are all implemented in a shared object libLTO. This allows | |
| the LLVM LTO code to be updated independently of the linker tool. On platforms | |
| that support it, the shared object is lazily loaded. | |
| Phase 2 : Symbol Resolution | |
| --------------------------- | |
| In this stage, the linker resolves symbols using global symbol table. It may | |
| report undefined symbol errors, read archive members, replace weak symbols, etc. | |
| The linker is able to do this seamlessly even though it does not know the exact | |
| content of input LLVM bitcode files. If dead code stripping is enabled then the | |
| linker collects the list of live symbols. | |
| Phase 3 : Optimize Bitcode Files | |
| -------------------------------- | |
| After symbol resolution, the linker tells the LTO shared object which symbols | |
| are needed by native object files. In the example above, the linker reports | |
| that only ``foo1()`` is used by native object files using | |
| ``lto_codegen_add_must_preserve_symbol()``. Next the linker invokes the LLVM | |
| optimizer and code generators using ``lto_codegen_compile()`` which returns a | |
| native object file creating by merging the LLVM bitcode files and applying | |
| various optimization passes. | |
| Phase 4 : Symbol Resolution after optimization | |
| ---------------------------------------------- | |
| In this phase, the linker reads optimized a native object file and updates the | |
| internal global symbol table to reflect any changes. The linker also collects | |
| information about any changes in use of external symbols by LLVM bitcode | |
| files. In the example above, the linker notes that ``foo4()`` is not used any | |
| more. If dead code stripping is enabled then the linker refreshes the live | |
| symbol information appropriately and performs dead code stripping. | |
| After this phase, the linker continues linking as if it never saw LLVM bitcode | |
| files. | |
| .. _libLTO: | |
| ``libLTO`` | |
| ========== | |
| ``libLTO`` is a shared object that is part of the LLVM tools, and is intended | |
| for use by a linker. ``libLTO`` provides an abstract C interface to use the LLVM | |
| interprocedural optimizer without exposing details of LLVM's internals. The | |
| intention is to keep the interface as stable as possible even when the LLVM | |
| optimizer continues to evolve. It should even be possible for a completely | |
| different compilation technology to provide a different libLTO that works with | |
| their object files and the standard linker tool. | |
| ``lto_module_t`` | |
| ---------------- | |
| A non-native object file is handled via an ``lto_module_t``. The following | |
| functions allow the linker to check if a file (on disk or in a memory buffer) is | |
| a file which libLTO can process: | |
| .. code-block:: c | |
| lto_module_is_object_file(const char*) | |
| lto_module_is_object_file_for_target(const char*, const char*) | |
| lto_module_is_object_file_in_memory(const void*, size_t) | |
| lto_module_is_object_file_in_memory_for_target(const void*, size_t, const char*) | |
| If the object file can be processed by ``libLTO``, the linker creates a | |
| ``lto_module_t`` by using one of: | |
| .. code-block:: c | |
| lto_module_create(const char*) | |
| lto_module_create_from_memory(const void*, size_t) | |
| and when done, the handle is released via | |
| .. code-block:: c | |
| lto_module_dispose(lto_module_t) | |
| The linker can introspect the non-native object file by getting the number of | |
| symbols and getting the name and attributes of each symbol via: | |
| .. code-block:: c | |
| lto_module_get_num_symbols(lto_module_t) | |
| lto_module_get_symbol_name(lto_module_t, unsigned int) | |
| lto_module_get_symbol_attribute(lto_module_t, unsigned int) | |
| The attributes of a symbol include the alignment, visibility, and kind. | |
| ``lto_code_gen_t`` | |
| ------------------ | |
| Once the linker has loaded each non-native object files into an | |
| ``lto_module_t``, it can request ``libLTO`` to process them all and generate a | |
| native object file. This is done in a couple of steps. First, a code generator | |
| is created with: | |
| .. code-block:: c | |
| lto_codegen_create() | |
| Then, each non-native object file is added to the code generator with: | |
| .. code-block:: c | |
| lto_codegen_add_module(lto_code_gen_t, lto_module_t) | |
| The linker then has the option of setting some codegen options. Whether or not | |
| to generate DWARF debug info is set with: | |
| .. code-block:: c | |
| lto_codegen_set_debug_model(lto_code_gen_t) | |
| which kind of position independence is set with: | |
| .. code-block:: c | |
| lto_codegen_set_pic_model(lto_code_gen_t) | |
| And each symbol that is referenced by a native object file or otherwise must not | |
| be optimized away is set with: | |
| .. code-block:: c | |
| lto_codegen_add_must_preserve_symbol(lto_code_gen_t, const char*) | |
| After all these settings are done, the linker requests that a native object file | |
| be created from the modules with the settings using: | |
| .. code-block:: c | |
| lto_codegen_compile(lto_code_gen_t, size*) | |
| which returns a pointer to a buffer containing the generated native object file. | |
| The linker then parses that and links it with the rest of the native object | |
| files. |