From e2c3a49c8029ebd9ef530101cc24c66562e3dff5 Mon Sep 17 00:00:00 2001 From: mike-m Date: Fri, 7 May 2010 00:28:04 +0000 Subject: Revert r103213. It broke several sections of live website. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103219 91177308-0d34-0410-b5e6-96231b3b80d8 --- docs/LinkTimeOptimization.html | 390 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 390 insertions(+) create mode 100644 docs/LinkTimeOptimization.html (limited to 'docs/LinkTimeOptimization.html') diff --git a/docs/LinkTimeOptimization.html b/docs/LinkTimeOptimization.html new file mode 100644 index 0000000000..1433d082ae --- /dev/null +++ b/docs/LinkTimeOptimization.html @@ -0,0 +1,390 @@ + + + + LLVM Link Time Optimization: Design and Implementation + + + +
+ LLVM Link Time Optimization: Design and Implementation +
+ + + +
+

Written by Devang Patel and Nick Kledzik

+
+ + +
+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 +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. +

+
+ + +
+ 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, + 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. +

+
+ + +
+ 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 + developements 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 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 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 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:

+ +
+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.

+
+ + +
+ 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:

+ +
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.

+ +
+ + + +
+
+ Valid CSS + Valid HTML 4.01 + + Devang Patel and Nick Kledzik
+ LLVM Compiler Infrastructure
+ Last modified: $Date$ +
+ + + + -- cgit v1.2.3