<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,
- llvm-gcc transparently invokes system linker. </p>
+ clang 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.
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 ---
#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
</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>
+
+<ul>
+ <li>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>.</li>
+ <li>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 also removes <tt>foo3()</tt>.</li>
+ <li>And this in turn, enables linker to remove <tt>foo4()</tt>.</li>
+</ul>
+
+<p>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">
+<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
</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
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
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">
+<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
</div>
<!-- ======================================================================= -->
-<div class="doc_subsection">
+<h3>
<a name="lto_code_gen_t">lto_code_gen_t</a>
-</div>
+</h3>
-<div class="doc_text">
+<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
</div>
+</div>
+
<!-- *********************************************************************** -->
<hr>
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