diff options
| author | Reid Spencer <rspencer@reidspencer.com> | 2006-08-14 19:19:55 +0000 |
|---|---|---|
| committer | Reid Spencer <rspencer@reidspencer.com> | 2006-08-14 19:19:55 +0000 |
| commit | b5fc9f537bd8dfe6c188ccf8e631807475d1a2f9 (patch) | |
| tree | ab3c9998f753397027541b35be68584a82c6f3cb /docs/LinkTimeOptimization.html | |
| parent | 61369da0e5461047adce93f3c3f5ca1ff49707fc (diff) | |
| download | llvm-b5fc9f537bd8dfe6c188ccf8e631807475d1a2f9.tar.gz llvm-b5fc9f537bd8dfe6c188ccf8e631807475d1a2f9.tar.bz2 llvm-b5fc9f537bd8dfe6c188ccf8e631807475d1a2f9.tar.xz | |
Fix several grammaros and a few HTML usage items.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@29665 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'docs/LinkTimeOptimization.html')
| -rw-r--r-- | docs/LinkTimeOptimization.html | 367 |
1 files changed, 180 insertions, 187 deletions
diff --git a/docs/LinkTimeOptimization.html b/docs/LinkTimeOptimization.html index 019ba7574d..f59ba59c1b 100644 --- a/docs/LinkTimeOptimization.html +++ b/docs/LinkTimeOptimization.html @@ -2,12 +2,12 @@ "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> @@ -45,11 +45,10 @@ <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 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> </div> <!-- *********************************************************************** --> @@ -60,16 +59,17 @@ intermodular optimizer and the linker and its design. <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 bytecode 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 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 the optimizer to avoid relying on +conservative escape analysis. </p> </div> @@ -79,72 +79,70 @@ optimizer to avoid relying on conservative escape analysis. </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.</p> + <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> +<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-gcc4 --emit-llvm -c a.c -o a.o # <-- a.o is LLVM bytecode file +$ llvm-gcc4 -c main.c -o main.o # <-- main.o is native object file +$ llvm-gcc4 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 byte code file. This information + is collected using <a href="#readllvmobjectfile"> readLLVMObjectFile()</a>. + Based on this information, 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> <!-- ======================================================================= --> @@ -153,27 +151,29 @@ optimizer can not remove <tt>foo3()</tt> without the linker's input. </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> <!-- *********************************************************************** --> @@ -182,17 +182,16 @@ time due to duplicate work done by this separate tool and linker itself. </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> @@ -202,16 +201,16 @@ optimizer by sharing this information during various linking phases. </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 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 <tt>dlopen()</tt>s the dynamic library. This is + to allow changes to the LLVM LTO code without relinking the linker. </p> </div> @@ -221,14 +220,14 @@ to allow changes to LLVM part without relinking the linker. </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 + 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 bytecode files because it uses + symbol information provided by + <a href="#readllvmobjectfile">readLLVMObjectFile()</a>. If dead code + stripping is enabled then the linker collects the list of live symbols. + </p> </div> <!-- ======================================================================= --> @@ -236,14 +235,14 @@ If dead code stripping is enabled then linker collects list of live symbols. <a name="phase3">Phase 3 : Optimize Bytecode 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 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 <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. </p> </div> @@ -253,17 +252,15 @@ optimized native object file of the LLVM portion of the program. </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 bytecode 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 + bytecode files.</p> </div> <!-- *********************************************************************** --> @@ -272,13 +269,11 @@ files. </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> + <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's internals. The intention is to keep the interface as stable as + possible even when the LLVM optimizer continues to evolve.</p> </div> <!-- ======================================================================= --> @@ -287,20 +282,20 @@ when the LLVM optimizer continues to evolve. </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>The <tt>LLVMSymbol</tt> class is used to describe the externally visible + functions and global variables, defined in LLVM bytecode 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 bytecode 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> <!-- ======================================================================= --> @@ -309,14 +304,13 @@ takes advantage of such information to generate better code. </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> + <p>The <tt>readLLVMObjectFile()</tt> function is used by the linker to read + LLVM bytecode files and collect LLVMSymbol nformation. This routine also + supplies a list of externally defined symbols that are used by LLVM bytecode + files. The 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 a list of external references used by + bytecode files.</p> </div> <!-- ======================================================================= --> @@ -325,12 +319,11 @@ function also provides list of external references used by bytecode file.<br> </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> + <p>The linker invokes <tt>optimizeModules</tt> to optimize already read + LLVM bytecode 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> <!-- *********************************************************************** --> @@ -341,7 +334,7 @@ as .o file at name and location provided by the linker. <div class="doc_text"> -<p><tt> ... incomplete ... </tt></p> +<p><tt> ... To be completed ... </tt></p> </div> |