+++ /dev/null
-<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
- "http://www.w3.org/TR/html4/strict.dtd">
-<html>
-<head>
- <title>LLVM Link Time Optimization: Design and Implementation</title>
- <link rel="stylesheet" href="llvm.css" type="text/css">
-</head>
-
-<div class="doc_title">
- LLVM Link Time Optimization: Design and Implementation
-</div>
-
-<ul>
- <li><a href="#desc">Description</a></li>
- <li><a href="#design">Design Philosophy</a>
- <ul>
- <li><a href="#example1">Example of link time optimization</a></li>
- <li><a href="#alternative_approaches">Alternative Approaches</a></li>
- </ul></li>
- <li><a href="#multiphase">Multi-phase communication between LLVM and linker</a>
- <ul>
- <li><a href="#phase1">Phase 1 : Read LLVM Bytecode Files</a></li>
- <li><a href="#phase2">Phase 2 : Symbol Resolution</a></li>
- <li><a href="#phase3">Phase 3 : Optimize Bitcode Files</a></li>
- <li><a href="#phase4">Phase 4 : Symbol Resolution after optimization</a></li>
- </ul></li>
- <li><a href="#lto">libLTO</a>
- <ul>
- <li><a href="#lto_module_t">lto_module_t</a></li>
- <li><a href="#lto_code_gen_t">lto_code_gen_t</a></li>
- </ul>
-</ul>
-
-<div class="doc_author">
-<p>Written by Devang Patel and Nick Kledzik</p>
-</div>
-
-<!-- *********************************************************************** -->
-<div class="doc_section">
-<a name="desc">Description</a>
-</div>
-<!-- *********************************************************************** -->
-
-<div class="doc_text">
-<p>
-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.</p>
-</div>
-
-<!-- *********************************************************************** -->
-<div class="doc_section">
-<a name="design">Design Philosophy</a>
-</div>
-<!-- *********************************************************************** -->
-
-<div class="doc_text">
-<p>
-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 <a href="#lto">libLTO</a>, 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.
-</p>
-</div>
-
-<!-- ======================================================================= -->
-<div class="doc_subsection">
- <a name="example1">Example of link time optimization</a>
-</div>
-
-<div class="doc_text">
- <p>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. </p>
- <ul>
- <li> Input source file <tt>a.c</tt> is compiled into LLVM bitcode form.
- <li> Input source file <tt>main.c</tt> is compiled into native object code.
- </ul>
-<pre class="doc_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 ---
-$ 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
-</pre>
- <p>In this example, the linker recognizes that <tt>foo2()</tt> is an
- externally visible symbol defined in LLVM bitcode file. The linker completes
- its usual symbol resolution
- pass and finds that <tt>foo2()</tt> is not used anywhere. This information
- is used by the LLVM optimizer and it removes <tt>foo2()</tt>. As soon as
- <tt>foo2()</tt> is removed, the optimizer recognizes that condition
- <tt>i < 0</tt> is always false, which means <tt>foo3()</tt> is never
- used. Hence, the optimizer removes <tt>foo3()</tt>, also. And this in turn,
- enables linker to remove <tt>foo4()</tt>. This example illustrates the
- advantage of tight integration with the linker. Here, the optimizer can not
- remove <tt>foo3()</tt> without the linker's input.
- </p>
-</div>
-
-<!-- ======================================================================= -->
-<div class="doc_subsection">
- <a name="alternative_approaches">Alternative Approaches</a>
-</div>
-
-<div class="doc_text">
- <dl>
- <dt><b>Compiler driver invokes link time optimizer separately.</b></dt>
- <dd>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 <tt>foo2()</tt> without
- the linker's input because it is externally visible. This in turn prohibits
- the optimizer from removing <tt>foo3()</tt>.</dd>
- <dt><b>Use separate tool to collect symbol information from all object
- files.</b></dt>
- <dd>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.
- </dd>
- </dl>
-</div>
-
-<!-- *********************************************************************** -->
-<div class="doc_section">
- <a name="multiphase">Multi-phase communication between libLTO and linker</a>
-</div>
-
-<div class="doc_text">
- <p>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.
-</p>
-</div>
-
-<!-- ======================================================================= -->
-<div class="doc_subsection">
- <a name="phase1">Phase 1 : Read LLVM Bitcode Files</a>
-</div>
-
-<div class="doc_text">
- <p>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 <tt>lto_module_create()</tt>
- when a supplied object file is found to not be a native object file. If
- <tt>lto_module_create()</tt> returns that the file is an LLVM bitcode file,
- the linker
- then iterates over the module using <tt>lto_module_get_symbol_name()</tt> and
- <tt>lto_module_get_symbol_attribute()</tt> to get all symbols defined and
- referenced.
- This information is added to the linker's global symbol table.
-</p>
- <p>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.
-</p>
-</div>
-
-<!-- ======================================================================= -->
-<div class="doc_subsection">
- <a name="phase2">Phase 2 : Symbol Resolution</a>
-</div>
-
-<div class="doc_text">
- <p>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.
- </p>
-</div>
-
-<!-- ======================================================================= -->
-<div class="doc_subsection">
- <a name="phase3">Phase 3 : Optimize Bitcode Files</a>
-</div>
-<div class="doc_text">
- <p>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 <tt>foo1()</tt> is used by native object files using
- <tt>lto_codegen_add_must_preserve_symbol()</tt>. Next the linker invokes
- the LLVM optimizer and code generators using <tt>lto_codegen_compile()</tt>
- which returns a native object file creating by merging the LLVM bitcode files
- and applying various optimization passes.
-</p>
-</div>
-
-<!-- ======================================================================= -->
-<div class="doc_subsection">
- <a name="phase4">Phase 4 : Symbol Resolution after optimization</a>
-</div>
-
-<div class="doc_text">
- <p>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
- <tt>foo4()</tt> 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.</p>
- <p>After this phase, the linker continues linking as if it never saw LLVM
- bitcode files.</p>
-</div>
-
-<!-- *********************************************************************** -->
-<div class="doc_section">
-<a name="lto">libLTO</a>
-</div>
-
-<div class="doc_text">
- <p><tt>libLTO</tt> is a shared object that is part of the LLVM tools, and
- is intended for use by a linker. <tt>libLTO</tt> 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.</p>
-</div>
-
-<!-- ======================================================================= -->
-<div class="doc_subsection">
- <a name="lto_module_t">lto_module_t</a>
-</div>
-
-<div class="doc_text">
-
-<p>A non-native object file is handled via an <tt>lto_module_t</tt>.
-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:</p>
-
-<pre class="doc_code">
-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*)
-</pre>
-
-<p>If the object file can be processed by libLTO, the linker creates a
-<tt>lto_module_t</tt> by using one of</p>
-
-<pre class="doc_code">
-lto_module_create(const char*)
-lto_module_create_from_memory(const void*, size_t)
-</pre>
-
-<p>and when done, the handle is released via</p>
-
-<pre class="doc_code">
-lto_module_dispose(lto_module_t)
-</pre>
-
-<p>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:</p>
-
-<pre class="doc_code">
-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)
-</pre>
-
-<p>The attributes of a symbol include the alignment, visibility, and kind.</p>
-</div>
-
-<!-- ======================================================================= -->
-<div class="doc_subsection">
- <a name="lto_code_gen_t">lto_code_gen_t</a>
-</div>
-
-<div class="doc_text">
-
-<p>Once the linker has loaded each non-native object files into an
-<tt>lto_module_t</tt>, 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:</p>
-
-<pre class="doc_code">lto_codegen_create()</pre>
-
-<p>Then, each non-native object file is added to the code generator with:</p>
-
-<pre class="doc_code">
-lto_codegen_add_module(lto_code_gen_t, lto_module_t)
-</pre>
-
-<p>The linker then has the option of setting some codegen options. Whether or
-not to generate DWARF debug info is set with:</p>
-
-<pre class="doc_code">lto_codegen_set_debug_model(lto_code_gen_t)</pre>
-
-<p>Which kind of position independence is set with:</p>
-
-<pre class="doc_code">lto_codegen_set_pic_model(lto_code_gen_t) </pre>
-
-<p>And each symbol that is referenced by a native object file or otherwise must
-not be optimized away is set with:</p>
-
-<pre class="doc_code">
-lto_codegen_add_must_preserve_symbol(lto_code_gen_t, const char*)
-</pre>
-
-<p>After all these settings are done, the linker requests that a native object
-file be created from the modules with the settings using:</p>
-
-<pre class="doc_code">lto_codegen_compile(lto_code_gen_t, size*)</pre>
-
-<p>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.</p>
-
-</div>
-
-<!-- *********************************************************************** -->
-
-<hr>
-<address>
- <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
- src="http://jigsaw.w3.org/css-validator/images/vcss-blue" alt="Valid CSS"></a>
- <a href="http://validator.w3.org/check/referer"><img
- src="http://www.w3.org/Icons/valid-html401-blue" alt="Valid HTML 4.01"></a>
-
- Devang Patel and Nick Kledzik<br>
- <a href="http://llvm.org">LLVM Compiler Infrastructure</a><br>
- Last modified: $Date$
-</address>
-
-</body>
-</html>
-
projects / oota-llvm.git / blobdiff