LLVM features powerful intermodular optimizations which can be used at link -time. Link Time Optimization is another name for intermodular optimization +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 LLVM intermodular optimizer and the linker.
+and design between the LTO optimizer and the linker.The following example illustrates the advantages of LTO's integrated - approach and clean interface.
+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, + llvm-gcc transparently invokes system linker.
+--- a.h --- extern int foo1(void); extern void foo2(void); @@ -126,14 +126,13 @@ int main() { } --- command lines --- -$ llvm-gcc4 --emit-llvm -c a.c -o a.o # <-- a.o is LLVM bytecode file -$ llvm-gcc4 -c main.c -o main.o # <-- main.o is native object file -$ llvm-gcc4 a.o main.o -o main # <-- standard link command without any modifications +$ llvm-gcc --emit-llvm -c a.c -o a.o # <-- a.o is LLVM bitcode file +$ llvm-gcc -c main.c -o main.o # <-- main.o is native object file +$ llvm-gcc a.o main.o -o main # <-- standard link command without any modificationsIn this example, the linker recognizes that foo2() is an - externally visible symbol defined in LLVM byte code file. This information - is collected using readLLVMObjectFile(). - Based on this information, the linker completes its usual symbol resolution + 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 @@ -178,7 +177,7 @@ $ llvm-gcc4 a.o main.o -o main # <-- standard link command without any modifi
- Multi-phase communication between LLVM and linker + Multi-phase communication between libLTO and linker@@ -197,20 +196,25 @@ $ llvm-gcc4 a.o main.o -o main # <-- standard link command without any modifi@@ -220,29 +224,26 @@ $ llvm-gcc4 a.o main.o -o main # <-- standard link command without any modifiThe linker first reads all object files in natural order and collects - symbol information. This includes native object files as well as LLVM byte - code files. In this phase, the linker uses - readLLVMObjectFile() to collect symbol - information from each LLVM bytecode files and updates its internal global - symbol table accordingly. The intent of this interface is to avoid overhead - in the non LLVM case, where all input object files are native object files, - by putting this code in the error path of the linker. When the linker sees - the first llvm .o file, it dlopen()s the dynamic library. This is - to allow changes to the LLVM LTO code without relinking the linker. + 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.
-In this stage, the linker resolves symbols using global symbol table - information to report undefined symbol errors, read archive members, resolve - weak symbols, etc. The linker is able to do this seamlessly even though it - does not know the exact content of input LLVM bytecode files because it uses - symbol information provided by - readLLVMObjectFile(). If dead code +
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.
-@@ -255,86 +256,118 @@ $ llvm-gcc4 a.o main.o -o main # <-- standard link command without any modifiAfter symbol resolution, the linker updates symbol information supplied - by LLVM bytecode files appropriately. For example, whether certain LLVM - bytecode supplied symbols are used or not. In the example above, the linker - reports that foo2() is not used anywhere in the program, including - native .o files. This information is used by the LLVM interprocedural - optimizer. The linker uses optimizeModules() - and requests an optimized native object file of the LLVM portion of the - program. +
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.
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 bytecode files. In the examle above, the linker notes that + LLVM bitcode files. In the examle 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 - bytecode files.
+ bitcode files.
LLVMlto is a dynamic library that is part of the LLVM tools, and - is intended for use by a linker. LLVMlto provides an abstract C++ +
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.
+ 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.The LLVMSymbol class is used to describe the externally visible - functions and global variables, defined in LLVM bytecode files, to the linker. - This includes symbol visibility information. This information is used by - the linker to do symbol resolution. For example: function foo2() is - defined inside an LLVM bytecode module and it is an externally visible symbol. - This helps the linker connect the use of foo2() in native object - files with a future definition of the symbol foo2(). The linker - will see the actual definition of foo2() when it receives the - optimized native object file in - Symbol Resolution after optimization phase. If the - linker does not find any uses of foo2(), it updates LLVMSymbol - visibility information to notify LLVM intermodular optimizer that it is dead. - The LLVM intermodular optimizer takes advantage of such information to - generate better code.
-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:
-The readLLVMObjectFile() function is used by the linker to read - LLVM bytecode files and collect LLVMSymbol nformation. This routine also - supplies a list of externally defined symbols that are used by LLVM bytecode - files. The linker uses this symbol information to do symbol resolution. - Internally, LLVMlto maintains LLVM bytecode modules in - memory. This function also provides a list of external references used by - bytecode files.
++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
+ ++lto_module_create(const char*) +lto_module_create_from_memory(const void*, size_t) ++ +
and when done, the handle is released via
+ ++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:
+ ++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.
The linker invokes optimizeModules to optimize already read - LLVM bytecode files by applying LLVM intermodular optimization techniques. - This function runs the LLVM intermodular optimizer and generates native - object code as .o files at the name and location provided by the - linker.
-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:
-lto_codegen_create()+ +
Then, each non-native object file is added to the code generator with:
+ ++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:
+ +lto_codegen_set_debug_model(lto_code_gen_t)+ +
Which kind of position independence is set with:
-... To be completed ...
+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:
+ ++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:
+ +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.
+ src="http://jigsaw.w3.org/css-validator/images/vcss-blue" alt="Valid CSS">