"http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
- <title>LLVM Link Time Optimization: design and implementation</title>
+ <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
+ LLVM Link Time Optimization: Design and Implementation
</div>
<ul>
<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 Bytecode Files</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">LLVMlto</a>
+ <li><a href="#lto">libLTO</a>
<ul>
- <li><a href="#llvmsymbol">LLVMSymbol</a></li>
- <li><a href="#readllvmobjectfile">readLLVMObjectFile()</a></li>
- <li><a href="#optimizemodules">optimizeModules()</a></li>
- </ul></li>
- <li><a href="#debug">Debugging Information</a></li>
+ <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</p>
+<p>Written by Devang Patel and Nick Kledzik</p>
</div>
<!-- *********************************************************************** -->
<div class="doc_text">
<p>
-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.
-</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_text">
<p>
-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
-<a href="#lto">LLVMlto</a>, 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.
+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>
<div class="doc_text">
-
-<p>Following example illustrates advantage of integrated approach that uses
-clean interface.
-<ul>
-<li> Input source file <tt>a.c</tt> is compiled into LLVM byte code form.
-<li> Input source file <tt>main.c</tt> is compiled into native object code.
-</ul>
-<code>
+ <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>
+<div class="doc_code"><pre>
--- a.h ---
-<br>extern int foo1(void);
-<br>extern void foo2(void);
-<br>extern void foo4(void);
-<br>--- a.c ---
-<br>#include "a.h"
-<br>
-<br>static signed int i = 0;
-<br>
-<br>void foo2(void) {
-<br> i = -1;
-<br>}
-<br>
-<br>static int foo3() {
-<br>foo4();
-<br>return 10;
-<br>}
-<br>
-<br>int foo1(void) {
-<br>int data = 0;
-<br>
-<br>if (i < 0) { data = foo3(); }
-<br>
-<br>data = data + 42;
-<br>return data;
-<br>}
-<br>
-<br>--- main.c ---
-<br>#include < stdio.h >
-<br>#include "a.h"
-<br>
-<br>void foo4(void) {
-<br> printf ("Hi\n");
-<br>}
-<br>
-<br>int main() {
-<br> return foo1();
-<br>}
-<br>
-<br>--- command lines ---
-<br> $ llvm-gcc4 --emit-llvm -c a.c -o a.o # <-- a.o is LLVM bytecode file
-<br> $ llvm-gcc4 -c main.c -o main.o # <-- main.o is native object file
-<br> $ llvm-gcc4 a.o main.o -o main # <-- standard link command without any modifications
-<br>
-</code>
-<p>
-In this example, the linker recognizes that <tt>foo2()</tt> is a externally visible
-symbol defined in LLVM byte code file. This information is collected using
-<a href="#readllvmobjectfile"> readLLVMObjectFile() </a>. Based on this
-information, linker completes its usual symbol resolution pass and finds that
-<tt>foo2()</tt> is not used anywhere. This information is used by LLVM optimizer
-and it removes <tt>foo2()</tt>. As soon as <tt>foo2()</tt> is removed, optimizer
-recognizes that condition <tt> i < 0 </tt> is always false, which means
-<tt>foo3()</tt> is never used. Hence, optimizer removes <tt>foo3()</tt> also.
-And this in turn, enables linker to remove <tt>foo4()</tt>.
-This example illustrates advantage of tight integration with linker. Here,
-optimizer can not remove <tt>foo3()</tt> without the linker's input.
-</p>
+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></div>
+ <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>
<div class="doc_text">
-<p>
-<ul>
-<li> Compiler driver invokes link time optimizer separately.
-<br><br>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 <tt>foo2()</tt> without linker's input because it is
-externally visible. And this in turn prohibits optimizer from removing <tt>foo3()</tt>.
-<br><br>
-<li> Use separate tool to collect symbol information from all object file.
-<br><br>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.
-</ul>
+ <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
+ maintance 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 LLVM and linker</a>
+ <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 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.
+ <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 intergration 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 Bytecode Files</a>
+ <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 byte code files.
-In this phase, the linker uses <a href="#readllvmobjectfile"> readLLVMObjectFile() </a>
-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.
+ <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>
<div class="doc_text">
-<p>
-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 <a href="#readllvmobjectfile"> readLLVMObjectFile() </a>.
-If dead code stripping is enabled then linker collects list of live symbols.
-</p>
+ <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 Bytecode Files</a>
+ <a name="phase3">Phase 3 : Optimize Bitcode Files</a>
</div>
<div class="doc_text">
-<p>
-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 <tt>foo2()</tt> is not used anywhere in the program, including native .o
-files. This information is used by LLVM interprocedural optimizer. The
-linker uses <a href="#optimizemodules"> optimizeModules()</a> and requests
-optimized native object file of the LLVM portion of the program.
+ <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>
<div class="doc_text">
-<p>
-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 <tt>foo4()</tt> is not used any more. If dead code
-striping is enabled then linker refreshes live symbol information appropriately
-and performs dead code stripping.
-<br>
-After this phase, the linker continues linking as if it never saw LLVM bytecode
-files.
-</p>
+ <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
+ <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">LLVMlto</a>
-</div>
-
-<div class="doc_text">
-<p>
-<tt>LLVMlto</tt> is a dynamic library that is part of the LLVM tools, and is
-intended for use by a linker. <tt>LLVMlto</tt> 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.
-</p>
-</div>
-
-<!-- ======================================================================= -->
-<div class="doc_subsection">
- <a name="llvmsymbol">LLVMSymbol</a>
+<a name="lto">libLTO</a>
</div>
<div class="doc_text">
-<p>
-<tt>LLVMSymbol</tt> 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 <tt>foo2()</tt> is defined inside
-a LLVM bytecode module and it is externally visible symbol.
-This helps linker connect use of <tt>foo2()</tt> in native object file with
-future definition of symbol <tt>foo2()</tt>. The linker will see actual definition
-of <tt>foo2()</tt> when it receives optimized native object file in <a href="#phase4">
-Symbol Resolution after optimization</a> phase. If the linker does not find any
-use of <tt>foo2()</tt>, 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.
-</p>
+ <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="readllvmobjectfile">readLLVMObjectFile()</a>
+ <a name="lto_module_t">lto_module_t</a>
</div>
<div class="doc_text">
-<p>
-<tt>readLLVMObjectFile()</tt> 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,
-<a href="#lto">LLVMlto</a> maintains LLVM bytecode modules in memory. This
-function also provides list of external references used by bytecode file.<br>
+ <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>
<!-- ======================================================================= -->
<div class="doc_subsection">
- <a name="optimizemodules">optimizeModules()</a>
-</div>
-
-<div class="doc_text">
-<p>
-The linker invokes <tt>optimizeModules</tt> 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.
-</p>
+ <a name="lto_code_gen_t">lto_code_gen_t</a>
</div>
-<!-- *********************************************************************** -->
-<div class="doc_section">
- <a name="debug">Debugging Information</a>
-</div>
-<!-- *********************************************************************** -->
-
<div class="doc_text">
-
-<p><tt> ... incomplete ... </tt></p>
-
+ <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>
<!-- *********************************************************************** -->
<a href="http://validator.w3.org/check/referer"><img
src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
- Devang Patel<br>
+ Devang Patel and Nick Kledzik<br>
<a href="http://llvm.org">LLVM Compiler Infrastructure</a><br>
Last modified: $Date$
</address>
</body>
</html>
+