From 721c201bd55ffb73cb2ba8d39e0570fa38c44e15 Mon Sep 17 00:00:00 2001 From: dim Date: Wed, 15 Aug 2012 19:34:23 +0000 Subject: Vendor import of llvm trunk r161861: http://llvm.org/svn/llvm-project/llvm/trunk@161861 --- docs/LinkTimeOptimization.html | 401 ----------------------------------------- 1 file changed, 401 deletions(-) delete mode 100644 docs/LinkTimeOptimization.html (limited to 'docs/LinkTimeOptimization.html') diff --git a/docs/LinkTimeOptimization.html b/docs/LinkTimeOptimization.html deleted file mode 100644 index 5652555..0000000 --- a/docs/LinkTimeOptimization.html +++ /dev/null @@ -1,401 +0,0 @@ - - - - - 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, - 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. -
-
---- 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 ---
-$ 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 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.

- -
- - -

- 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: 2011-10-31 12:21:59 +0100 (Mon, 31 Oct 2011) $ -
- - - - -- cgit v1.1