From 93449f13d8f928824a9e200ae3e57d1e0a371c02 Mon Sep 17 00:00:00 2001 From: Devang Patel Date: Mon, 14 Aug 2006 18:03:40 +0000 Subject: [PATCH] Add lto doc. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@29659 91177308-0d34-0410-b5e6-96231b3b80d8 --- docs/LinkTimeOptimization.html | 361 +++++++++++++++++++++++++++++++++ 1 file changed, 361 insertions(+) create mode 100644 docs/LinkTimeOptimization.html diff --git a/docs/LinkTimeOptimization.html b/docs/LinkTimeOptimization.html new file mode 100644 index 00000000000..f3a61185938 --- /dev/null +++ b/docs/LinkTimeOptimization.html @@ -0,0 +1,361 @@ + + + + LLVM Link Time Optimization: design and implementation + + + +
+ LLVM Link Time Optimization: design and implentation +
+ + + +
+

Written by Devang Patel

+
+ + +
+Description +
+ + +
+

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

+
+ + +
+Design Philosophy +
+ + +
+

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

+ + +
+ Example of link time optimization +
+ +
+ +

Following example illustrates advantage of integrated approach that uses +clean interface. +

  • Input source file a.c is compiled into LLVM byte code form. +
  • Input source file main.c is compiled into native object code. +
    + +
    --- 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. +

    +
    • + + +
    + Alternative Approaches +
    + +
    +

    +

  • Compiler driver invokes link time optimizer separately. +

    In this model link time optimizer is not able to take advantage of information +collected during normal linker's symbol resolution phase. In above example, +optimizer can not remove foo2() without linker's input because it is +externally visible. And this in turn prohibits optimizer from removing foo3(). +

    +
  • Use separate tool to collect symbol information from all object file. +

    In this model, this new separate tool or library replicates linker's +capabilities to collect information for link time optimizer. Not only such code +duplication is difficult to justify but it also has several other disadvantages. +For example, the linking semantics and the features provided by 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 one new separate tool per +platform is required. This increases maintance cost for link time optimizer +significantly, which is not necessary. Plus, this approach requires staying +synchronized with linker developements on various platforms, which is not the +main focus of link time optimizer. Finally, this approach increases end user's build +time due to duplicate work done by this separate tool and linker itself. +

    +
    • + + +
    + Multi-phase communication between LLVM 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 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. +

    +
    + + +
    + Phase 1 : Read LLVM Bytecode Files +
    + +
    +

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

    +
    + + +
    + Phase 2 : Symbol Resolution +
    + +
    +

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

    +
    + + +
    + Phase 3 : Optimize Bytecode Files +
    +
    +

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

    +
    + + +
    + Phase 4 : Symbol Resolution after optimization +
    + +
    +

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

    +
    + + +
    +LLVMlto +
    + +
    +

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

    +
    + + +
    + LLVMSymbol +
    + +
    +

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

    +
    + + +
    + readLLVMObjectFile() +
    + +
    +

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

    +
    + + +
    + optimizeModules() +
    + +
    +

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

    +
    + + +
    + Debugging Information +
    + + +
    + +

    ... incomplete ...

    + +
    + + + +
    +
    + Valid CSS! + Valid HTML 4.01! + + Devang Patel
    + LLVM Compiler Infrastructure
    + Last modified: $Date$ +
    + + + -- 2.34.1