<link rel="stylesheet" href="llvm.css" type="text/css">
</head>
-<div class="doc_title">
+<h1>
LLVM Link Time Optimization: Design and Implementation
-</div>
+</h1>
<ul>
<li><a href="#desc">Description</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="#phase1">Phase 1 : Read LLVM Bitcode 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>
</div>
<!-- *********************************************************************** -->
-<div class="doc_section">
+<h2>
<a name="desc">Description</a>
-</div>
+</h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>
LLVM features powerful intermodular optimizations which can be used at link
time. Link Time Optimization (LTO) is another name for intermodular optimization
</div>
<!-- *********************************************************************** -->
-<div class="doc_section">
+<h2>
<a name="design">Design Philosophy</a>
-</div>
+</h2>
<!-- *********************************************************************** -->
-<div class="doc_text">
+<div>
<p>
The LLVM Link Time Optimizer provides complete transparency, while doing
intermodular optimization, in the compiler tool chain. Its main goal is to let
in other models. The linker input allows the optimizer to avoid relying on
conservative escape analysis.
</p>
-</div>
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="example1">Example of link time optimization</a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<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,
<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>
-<div class="doc_code"><pre>
+<pre class="doc_code">
--- a.h ---
extern int foo1(void);
extern void foo2(void);
$ 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></div>
+</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
</div>
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="alternative_approaches">Alternative Approaches</a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<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
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
- maintance cost for link time optimizer significantly, which is not
+ 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
</dl>
</div>
+</div>
+
<!-- *********************************************************************** -->
-<div class="doc_section">
+<h2>
<a name="multiphase">Multi-phase communication between libLTO and linker</a>
-</div>
+</h2>
-<div class="doc_text">
+<div>
<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
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 intergration between the linker and
+ 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">
+<h3>
<a name="phase1">Phase 1 : Read LLVM Bitcode Files</a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<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
</div>
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="phase2">Phase 2 : Symbol Resolution</a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<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
</div>
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="phase3">Phase 3 : Optimize Bitcode Files</a>
-</div>
-<div class="doc_text">
+</h3>
+<div>
<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
</div>
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="phase4">Phase 4 : Symbol Resolution after optimization</a>
-</div>
+</h3>
-<div class="doc_text">
+<div>
<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 examle above, the linker notes that
+ 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>
bitcode files.</p>
</div>
+</div>
+
<!-- *********************************************************************** -->
-<div class="doc_section">
+<h2>
<a name="lto">libLTO</a>
-</div>
+</h2>
-<div class="doc_text">
+<div>
<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
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">
+<h3>
<a name="lto_module_t">lto_module_t</a>
-</div>
+</h3>
-<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: <pre>
- 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>
- If the object file can be processed by libLTO, the linker creates a
- <tt>lto_module_t</tt> by using one of <pre>
- lto_module_create(const char*)
- lto_module_create_from_memory(const void*, size_t)</pre>
- and when done, the handle is released via<pre>
- lto_module_dispose(lto_module_t)</pre>
- 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: <pre>
- 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>
- The attributes of a symbol include the alignment, visibility, and kind.
-</p>
+<div>
+
+<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">
+<h3>
<a name="lto_code_gen_t">lto_code_gen_t</a>
+</h3>
+
+<div>
+
+<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>
-<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:<pre>
- lto_codegen_create() </pre>
- then each non-native object file is added to the code generator with:<pre>
- lto_codegen_add_module(lto_code_gen_t, lto_module_t)</pre>
- The linker then has the option of setting some codegen options. Whether
- or not to generate DWARF debug info is set with: <pre>
- lto_codegen_set_debug_model(lto_code_gen_t) </pre>
- Which kind of position independence is set with: <pre>
- lto_codegen_set_pic_model(lto_code_gen_t) </pre>
- And each symbol that is referenced by a native object file or otherwise
- must not be optimized away is set with: <pre>
- lto_codegen_add_must_preserve_symbol(lto_code_gen_t, const char*)</pre>
- 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*)</pre>
- 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.
</div>
<!-- *********************************************************************** -->
<hr>
<address>
<a href="http://jigsaw.w3.org/css-validator/check/referer"><img
- src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
+ 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" alt="Valid HTML 4.01!"></a>
+ 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>
+ <a href="http://llvm.org/">LLVM Compiler Infrastructure</a><br>
Last modified: $Date$
</address>
projects / oota-llvm.git / blobdiff