diff options
| -rw-r--r-- | docs/LinkTimeOptimization.html | 401 | ||||
| -rw-r--r-- | docs/LinkTimeOptimization.rst | 298 | ||||
| -rw-r--r-- | docs/subsystems.rst | 3 |
3 files changed, 300 insertions, 402 deletions
diff --git a/docs/LinkTimeOptimization.html b/docs/LinkTimeOptimization.html deleted file mode 100644 index 8063fa8510..0000000000 --- a/docs/LinkTimeOptimization.html +++ /dev/null @@ -1,401 +0,0 @@ -<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" - "http://www.w3.org/TR/html4/strict.dtd"> -<html> -<head> - <meta http-equiv="Content-Type" content="text/html; charset=utf-8"> - <title>LLVM Link Time Optimization: Design and Implementation</title> - <link rel="stylesheet" href="_static/llvm.css" type="text/css"> -</head> - -<h1> - LLVM Link Time Optimization: Design and Implementation -</h1> - -<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 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> - </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> - -<!-- *********************************************************************** --> -<h2> -<a name="desc">Description</a> -</h2> -<!-- *********************************************************************** --> - -<div> -<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> - -<!-- *********************************************************************** --> -<h2> -<a name="design">Design Philosophy</a> -</h2> -<!-- *********************************************************************** --> - -<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 -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> - -<!-- ======================================================================= --> -<h3> - <a name="example1">Example of link time optimization</a> -</h3> - -<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, - 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. - </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 --- -$ 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> - -<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> - -<!-- ======================================================================= --> -<h3> - <a name="alternative_approaches">Alternative Approaches</a> -</h3> - -<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 - 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> - -<!-- *********************************************************************** --> -<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 - 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> - -<!-- ======================================================================= --> -<h3> - <a name="phase1">Phase 1 : Read LLVM Bitcode Files</a> -</h3> - -<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 - 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> - -<!-- ======================================================================= --> -<h3> - <a name="phase2">Phase 2 : Symbol Resolution</a> -</h3> - -<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> - -<!-- ======================================================================= --> -<h3> - <a name="phase3">Phase 3 : Optimize Bitcode Files</a> -</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> - -<!-- ======================================================================= --> -<h3> - <a name="phase4">Phase 4 : Symbol Resolution after optimization</a> -</h3> - -<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 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> - -<!-- *********************************************************************** --> -<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. 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> - -<!-- ======================================================================= --> -<h3> - <a name="lto_module_t">lto_module_t</a> -</h3> - -<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> - -<!-- ======================================================================= --> -<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> - -<!-- *********************************************************************** --> - -<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> - diff --git a/docs/LinkTimeOptimization.rst b/docs/LinkTimeOptimization.rst new file mode 100644 index 0000000000..53d673e406 --- /dev/null +++ b/docs/LinkTimeOptimization.rst @@ -0,0 +1,298 @@ +.. _lto: + +====================================================== +LLVM Link Time Optimization: Design and Implementation +====================================================== + +.. contents:: + :local: + +Description +=========== + +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. + +Design Philosophy +================= + +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 `libLTO`_, 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. + +Example of link time optimization +--------------------------------- + +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, clang transparently +invokes system linker. + +* Input source file ``a.c`` is compiled into LLVM bitcode form. +* Input source file ``main.c`` is compiled into native object code. + +.. code-block:: c++ + + --- 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(); + } + +.. code-block:: bash + + --- command lines --- + % 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 modifications + +* In this example, the linker recognizes that ``foo2()`` is an externally + visible symbol defined in LLVM bitcode file. The linker completes its usual + symbol resolution pass and finds that ``foo2()`` is not used + anywhere. This information is used by the LLVM optimizer and it + removes ``foo2()``.</li> + +* As soon as ``foo2()`` is removed, the optimizer recognizes that condition ``i + < 0`` is always false, which means ``foo3()`` is never used. Hence, the + optimizer also removes ``foo3()``. + +* And this in turn, enables linker to remove ``foo4()``. + +This example illustrates the advantage of tight integration with the +linker. Here, the optimizer can not remove ``foo3()`` without the linker's +input. + +Alternative Approaches +---------------------- + +**Compiler driver invokes link time optimizer separately.** + 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 ``foo2()`` without the + linker's input because it is externally visible. This in turn prohibits the + optimizer from removing ``foo3()``. + +**Use separate tool to collect symbol information from all object files.** + 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. + +Multi-phase communication between ``libLTO`` and linker +======================================================= + +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. + +Phase 1 : Read LLVM Bitcode Files +--------------------------------- + +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 ``lto_module_create()`` when a supplied +object file is found to not be a native object file. If ``lto_module_create()`` +returns that the file is an LLVM bitcode file, the linker then iterates over the +module using ``lto_module_get_symbol_name()`` and +``lto_module_get_symbol_attribute()`` to get all symbols defined and referenced. +This information is added to the linker's global symbol table. + + +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. + +Phase 2 : Symbol Resolution +--------------------------- + +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. + +Phase 3 : Optimize Bitcode Files +-------------------------------- + +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 ``foo1()`` is used by native object files using +``lto_codegen_add_must_preserve_symbol()``. Next the linker invokes the LLVM +optimizer and code generators using ``lto_codegen_compile()`` which returns a +native object file creating by merging the LLVM bitcode files and applying +various optimization passes. + +Phase 4 : Symbol Resolution after optimization +---------------------------------------------- + +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 ``foo4()`` 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. + +After this phase, the linker continues linking as if it never saw LLVM bitcode +files. + +.. _libLTO: + +``libLTO`` +========== + +``libLTO`` is a shared object that is part of the LLVM tools, and is intended +for use by a linker. ``libLTO`` 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. + +``lto_module_t`` +---------------- + +A non-native object file is handled via an ``lto_module_t``. 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: + +.. code-block:: c + + 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*) + +If the object file can be processed by ``libLTO``, the linker creates a +``lto_module_t`` by using one of: + +.. code-block:: c + + lto_module_create(const char*) + lto_module_create_from_memory(const void*, size_t) + +and when done, the handle is released via + +.. code-block:: c + + lto_module_dispose(lto_module_t) + + +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: + +.. code-block:: c + + 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) + +The attributes of a symbol include the alignment, visibility, and kind. + +``lto_code_gen_t`` +------------------ + +Once the linker has loaded each non-native object files into an +``lto_module_t``, 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: + +.. code-block:: c + + lto_codegen_create() + +Then, each non-native object file is added to the code generator with: + +.. code-block:: c + + lto_codegen_add_module(lto_code_gen_t, lto_module_t) + +The linker then has the option of setting some codegen options. Whether or not +to generate DWARF debug info is set with: + +.. code-block:: c + + lto_codegen_set_debug_model(lto_code_gen_t) + +Which kind of position independence is set with: + +.. code-block:: c + + lto_codegen_set_pic_model(lto_code_gen_t) + +And each symbol that is referenced by a native object file or otherwise must not +be optimized away is set with: + +.. code-block:: c + + lto_codegen_add_must_preserve_symbol(lto_code_gen_t, const char*) + +After all these settings are done, the linker requests that a native object file +be created from the modules with the settings using: + +.. code-block:: c + + lto_codegen_compile(lto_code_gen_t, size*) + +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. diff --git a/docs/subsystems.rst b/docs/subsystems.rst index d7db6fcfce..ee0c2bedd0 100644 --- a/docs/subsystems.rst +++ b/docs/subsystems.rst @@ -7,6 +7,7 @@ Subsystem Documentation :hidden: AliasAnalysis + LinkTimeOptimization * `Writing an LLVM Pass <WritingAnLLVMPass.html>`_ @@ -61,7 +62,7 @@ Subsystem Documentation This document describes the LLVM System Library (<tt>lib/System</tt>) and how to keep LLVM source code portable -* `Link Time Optimization <LinkTimeOptimization.html>`_ +* :ref:`lto` This document describes the interface between LLVM intermodular optimizer and the linker and its design |