-LLVM features powerful intermodular optimization which can be used at link time. -Link Time Optimization is another name of intermodular optimization when it -is done during link stage. This document describes the interface between LLVM -intermodular optimizer and the linker and its design. -
+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.-The LLVM Link Time Optimizer seeks complete transparency, while doing intermodular -optimization, in compiler tool chain. Its main goal is to let developer take -advantage of intermodular optimizer without making any significant changes to -their makefiles or build system. This is achieved through tight integration with -linker. In this model, linker treates LLVM bytecode files like native objects -file and allows mixing and matching among them. The linker uses -LLVMlto, a dynamically loaded library, to handle LLVM bytecode -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 -optimizer to avoid relying on conservative escape analysis. +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 +treates 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.
+Following example illustrates advantage of integrated approach that uses -clean interface. -
-
--- 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
-
#include "a.h"
-
-
void foo4(void) {
-
printf ("Hi\n");
-
}
-
-
int main() {
-
return foo1();
-
}
-
-
--- 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
-
-
-
--In this example, the linker recognizes that foo2() is a externally visible -symbol defined in LLVM byte code file. This information is collected using - readLLVMByteCodeFile() . Based on this -information, linker completes its usual symbol resolution pass and finds that -foo2() is not used anywhere. This information is used by LLVM optimizer -and it removes foo2(). As soon as foo2() is removed, optimizer -recognizes that condition i < 0 is always false, which means -foo3() is never used. Hence, optimizer removes foo3() also. -And this in turn, enables linker to remove foo4(). -This example illustrates advantage of tight integration with linker. Here, -optimizer can not remove foo3() without the linker's input. -
+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);
+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();
+}
+
+--- command lines ---
+$ 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 modifications
+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 removes foo3(), also. 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. +
-
-The linker collects information about symbol defininitions and uses in various -link objects which is more accurate than any information collected by other tools -during typical build cycle. -The linker collects this information by looking at definitions and uses of -symbols in native .o files and using symbol visibility information. The linker -also uses user supplied information, such as list of exported symbol. -LLVM optimizer collects control flow information, data flow information and -knows much more about program structure from optimizer's point of view. Our -goal is to take advantage of tight intergration between the linker and -optimizer by sharing this information during various linking phases. +
The linker collects information about symbol defininitions 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 intergration between the linker and + the optimizer by sharing this information during various linking phases.
-The 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 readLLVMByteCodeFile() -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 LLVM part without relinking the linker. +
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.
-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 exact content of input LLVM bytecode files because it uses symbol information -provided by readLLVMByteCodeFile() . -If dead code stripping is enabled then linker collects list of live symbols. -
+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. +
-After 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 LLVM interprocedural optimizer. The -linker uses optimizeModules() and requests -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 native object file and updates internal
-global symbol table to reflect any changes. Linker also collects information
-about any change in use of external symbols by LLVM bytecode files. In the examle
-above, the linker notes that foo4() is not used any more. If dead code
-striping is enabled then linker refreshes live symbol information appropriately
-and performs dead code stripping.
-
-After this phase, the linker continues linking as if it never saw LLVM bytecode
-files.
-
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 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 + 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++ interface -to use the LLVM interprocedural optimizer without exposing details of LLVM -internals. The intention is to keep the interface as stable as possible even -when the LLVM optimizer continues to evolve. -
+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.
-LLVMSymbol class is used to describe the externally visible functions -and global variables, tdefined in LLVM bytecode files, to linker. -This includes symbol visibility information. This information is used by linker -to do symbol resolution. For example : function foo2() is defined inside -a LLVM bytecode module and it is externally visible symbol. -This helps linker connect use of foo2() in native object file with -future definition of symbol foo2(). The linker will see actual definition -of foo2() when it receives optimized native object file in -Symbol Resolution after optimization phase. If the linker does not find any -use 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:
+ 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.
-readLLVMObjectFile() is used by the linker to read LLVM bytecode files
-and collect LLVMSymbol nformation. This routine also
-supplies list of externally defined symbols that are used by LLVM bytecode
-files. Linker uses this symbol information to do symbol resolution. Internally,
-LLVMlto maintains LLVM bytecode modules in memory. This
-function also provides list of external references used by bytecode file.
-
-The linker invokes optimizeModules to optimize already read LLVM -bytecode files by applying LLVM intermodular optimization techniques. This -function runs LLVM intermodular optimizer and generates native object code -as .o file at name and location provided by the linker. -
-... incomplete ...
- +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:
+ 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.