<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 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>
- <li><a href="#gettargettriple">getTargetTriple()</a></li>
- <li><a href="#removemodule">removeModule()</a></li>
- <li><a href="#getalignment">getAlignment()</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_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 is another name for intermodular optimization
+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 LLVM intermodular optimizer and the linker.</p>
+and design between the LTO optimizer and the linker.</p>
</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
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">LLVMlto</a>, a dynamically
-loaded library, to handle LLVM bitcode files. This tight integration between
+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">
+<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. This information
- is collected using <a href="#readllvmobjectfile"> readLLVMObjectFile()</a>.
- Based on this information, the linker completes its usual symbol resolution
+ 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
</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 class="doc_section">
- <a name="multiphase">Multi-phase communication between LLVM and linker</a>
</div>
-<div class="doc_text">
+<!-- *********************************************************************** -->
+<h2>
+ <a name="multiphase">Multi-phase communication between libLTO and linker</a>
+</h2>
+
+<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. In this phase, the linker uses
- <a href="#readllvmobjectfile"> readLLVMObjectFile() </a> to collect symbol
- information from each LLVM bitcode 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 <tt>dlopen()</tt>s the dynamic library. This is
- to allow changes to the LLVM LTO code without relinking the linker.
+ 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">
+<h3>
<a name="phase2">Phase 2 : Symbol Resolution</a>
-</div>
+</h3>
-<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 the exact content of input LLVM bitcode files because it uses
- symbol information provided by
- <a href="#readllvmobjectfile">readLLVMObjectFile()</a>. If dead code
+<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
+ 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">
+<h3>
<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 bitcode files appropriately. For example, whether certain LLVM
- bitcode 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 <tt>.o</tt> files. This information is used by the LLVM interprocedural
- optimizer. The linker uses <a href="#optimizemodules">optimizeModules()</a>
- and requests an optimized native object file of the LLVM portion of the
- program.
+</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
+ <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">
+<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 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++
+<!-- *********************************************************************** -->
+<h2>
+<a name="lto">libLTO</a>
+</h2>
+
+<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
of LLVM's internals. The intention is to keep the interface as stable as
- possible even when the LLVM optimizer continues to evolve.</p>
-</div>
+ 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 class="doc_subsection">
- <a name="llvmsymbol">LLVMSymbol</a>
-</div>
+<h3>
+ <a name="lto_module_t">lto_module_t</a>
+</h3>
-<div class="doc_text">
- <p>The <tt>LLVMSymbol</tt> class is used to describe the externally visible
- functions and global variables, defined in LLVM bitcode files, to the linker.
- This includes symbol visibility information. This information is used by
- the linker to do symbol resolution. For example: function <tt>foo2()</tt> is
- defined inside an LLVM bitcode module and it is an externally visible symbol.
- This helps the linker connect the use of <tt>foo2()</tt> in native object
- files with a future definition of the symbol <tt>foo2()</tt>. The linker
- will see the actual definition of <tt>foo2()</tt> when it receives the
- optimized native object file in
- <a href="#phase4">Symbol Resolution after optimization</a> phase. If the
- linker does not find any uses 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>
-</div>
+<div>
-<!-- ======================================================================= -->
-<div class="doc_subsection">
- <a name="readllvmobjectfile">readLLVMObjectFile()</a>
-</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>
-<div class="doc_text">
- <p>The <tt>readLLVMObjectFile()</tt> function is used by the linker to read
- LLVM bitcode files and collect LLVMSymbol information. This routine also
- supplies a list of externally defined symbols that are used by LLVM bitcode
- files. The linker uses this symbol information to do symbol resolution.
- Internally, <a href="#lto">LLVMlto</a> maintains LLVM bitcode modules in
- memory. This function also provides a list of external references used by
- bitcode files.</p>
-</div>
+<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>
-<!-- ======================================================================= -->
-<div class="doc_subsection">
- <a name="optimizemodules">optimizeModules()</a>
-</div>
+<p>If the object file can be processed by libLTO, the linker creates a
+<tt>lto_module_t</tt> by using one of</p>
-<div class="doc_text">
- <p>The linker invokes <tt>optimizeModules</tt> to optimize already read
- LLVM bitcode files by applying LLVM intermodular optimization techniques.
- This function runs the LLVM intermodular optimizer and generates native
- object code as <tt>.o</tt> files at the name and location provided by the
- linker.</p>
-</div>
+<pre class="doc_code">
+lto_module_create(const char*)
+lto_module_create_from_memory(const void*, size_t)
+</pre>
-<!-- ======================================================================= -->
-<div class="doc_subsection">
- <a name="gettargettriple">getTargetTriple()</a>
-</div>
+<p>and when done, the handle is released via</p>
-<div class="doc_text">
- <p>The linker may use <tt>getTargetTriple()</tt> to query target architecture
- while validating LLVM bitcode file.</p>
-</div>
+<pre class="doc_code">
+lto_module_dispose(lto_module_t)
+</pre>
-<!-- ======================================================================= -->
-<div class="doc_subsection">
- <a name="removemodule">removeModule()</a>
-</div>
+<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>
-<div class="doc_text">
- <p>Internally, <a href="#lto">LLVMlto</a> maintains LLVM bitcode modules in
- memory. The linker may use <tt>removeModule()</tt> method to remove desired
- modules from memory. </p>
+<p>The attributes of a symbol include the alignment, visibility, and kind.</p>
</div>
<!-- ======================================================================= -->
-<div class="doc_subsection">
- <a name="getalignment">getAlignment()</a>
-</div>
+<h3>
+ <a name="lto_code_gen_t">lto_code_gen_t</a>
+</h3>
-<div class="doc_text">
- <p>The linker may use <a href="#llvmsymbol">LLVMSymbol</a> method
- <tt>getAlignment()</tt> to query symbol alignment information.</p>
-</div>
+<div>
-<!-- *********************************************************************** -->
-<div class="doc_section">
- <a name="debug">Debugging Information</a>
-</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>
-<div class="doc_text">
+<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>
-<p><tt> ... To be completed ... </tt></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>
<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<br>
- <a href="http://llvm.org">LLVM Compiler Infrastructure</a><br>
+ 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