X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=docs%2FLinkTimeOptimization.html;h=c9c78b913c704be46f05f04757570c94eaf050b6;hb=39fe397421a23ea44e19b991e64b04f335f7bde6;hp=720a5e460ab53eb668f5bc4b3779bdcb76a9de54;hpb=05d0265fef651de152c8127aa701e689555649f3;p=oota-llvm.git diff --git a/docs/LinkTimeOptimization.html b/docs/LinkTimeOptimization.html index 720a5e460ab..c9c78b913c7 100644 --- a/docs/LinkTimeOptimization.html +++ b/docs/LinkTimeOptimization.html @@ -2,6 +2,7 @@ "http://www.w3.org/TR/html4/strict.dtd"> + LLVM Link Time Optimization: Design and Implementation @@ -41,7 +42,7 @@ -
+

LLVM features powerful intermodular optimizations which can be used at link time. Link Time Optimization (LTO) is another name for intermodular optimization @@ -55,7 +56,7 @@ and design between the LTO optimizer and the linker.

-
+

The LLVM Link Time Optimizer provides complete transparency, while doing intermodular optimization, in the compiler tool chain. Its main goal is to let @@ -69,18 +70,17 @@ 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.

+ 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. @@ -90,27 +90,29 @@ conservative escape analysis. 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; + i = -1; } static int foo3() { -foo4(); -return 10; + foo4(); + return 10; } int foo1(void) { -int data = 0; + int data = 0; -if (i < 0) { data = foo3(); } + if (i < 0) + data = foo3(); -data = data + 42; -return data; + data = data + 42; + return data; } --- main.c --- @@ -118,30 +120,35 @@ return data; #include "a.h" void foo4(void) { - printf ("Hi\n"); + printf("Hi\n"); } int main() { - return foo1(); + 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 +$ clang -emit-llvm -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 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. -

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

    +
@@ -149,7 +156,7 @@ $ llvm-gcc a.o main.o -o main # <-- standard link command without any modific Alternative Approaches -
+
Compiler driver invokes link time optimizer separately.
In this model the link time optimizer is not able to take advantage of @@ -175,12 +182,14 @@ $ llvm-gcc a.o main.o -o main # <-- standard link command without any modific
+
+

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 @@ -192,14 +201,13 @@ $ llvm-gcc a.o main.o -o main # <-- standard link command without any modific 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 @@ -223,7 +231,7 @@ $ llvm-gcc a.o main.o -o main # <-- standard link command without any modific 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 @@ -236,7 +244,7 @@ $ llvm-gcc a.o main.o -o main # <-- standard link command without any modific

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 @@ -252,7 +260,7 @@ $ llvm-gcc a.o main.o -o main # <-- standard link command without any modific 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 @@ -264,12 +272,14 @@ $ llvm-gcc a.o main.o -o main # <-- standard link command without any modific 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 @@ -278,14 +288,13 @@ $ llvm-gcc a.o main.o -o main # <-- standard link command without any modific 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 @@ -329,7 +338,7 @@ lto_module_get_symbol_attribute(lto_module_t, unsigned int) 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 @@ -371,6 +380,8 @@ of the native object files.

+
+