It's not necessary to do rounding for alloca operations when the requested
alignment is equal to the stack alignment.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@40004 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/docs/LinkTimeOptimization.html b/docs/LinkTimeOptimization.html
new file mode 100644
index 0000000..fdae78a
--- /dev/null
+++ b/docs/LinkTimeOptimization.html
@@ -0,0 +1,392 @@
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
+ "http://www.w3.org/TR/html4/strict.dtd">
+<html>
+<head>
+ <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
+</div>
+
+<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 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="#phase4">Phase 4 : Symbol Resolution after optimization</a></li>
+ </ul></li>
+ <li><a href="#lto">LLVMlto</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>
+</ul>
+
+<div class="doc_author">
+<p>Written by Devang Patel</p>
+</div>
+
+<!-- *********************************************************************** -->
+<div class="doc_section">
+<a name="desc">Description</a>
+</div>
+<!-- *********************************************************************** -->
+
+<div class="doc_text">
+<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>
+
+<!-- *********************************************************************** -->
+<div class="doc_section">
+<a name="design">Design Philosophy</a>
+</div>
+<!-- *********************************************************************** -->
+
+<div class="doc_text">
+<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">LLVMlto</a>, a dynamically
+loaded library, 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">
+ <a name="example1">Example of link time optimization</a>
+</div>
+
+<div class="doc_text">
+ <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-gcc4 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 ---
+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 bitcode 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></div>
+ <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
+ 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 class="doc_subsection">
+ <a name="alternative_approaches">Alternative Approaches</a>
+</div>
+
+<div class="doc_text">
+ <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>
+</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 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 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 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.
+</p>
+</div>
+
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <a name="phase2">Phase 2 : Symbol Resolution</a>
+</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 the exact content of input LLVM bitcode 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>
+
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <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.
+</p>
+</div>
+
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <a name="phase4">Phase 4 : Symbol Resolution after optimization</a>
+</div>
+
+<div class="doc_text">
+ <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's 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>
+</div>
+
+<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 class="doc_subsection">
+ <a name="readllvmobjectfile">readLLVMObjectFile()</a>
+</div>
+
+<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>
+
+<!-- ======================================================================= -->
+<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 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>
+
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <a name="gettargettriple">getTargetTriple()</a>
+</div>
+
+<div class="doc_text">
+ <p>The linker may use <tt>getTargetTriple()</tt> to query target architecture
+ while validating LLVM bitcode file.</p>
+</div>
+
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <a name="removemodule">removeModule()</a>
+</div>
+
+<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>
+</div>
+
+<!-- ======================================================================= -->
+<div class="doc_subsection">
+ <a name="getalignment">getAlignment()</a>
+</div>
+
+<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 class="doc_section">
+ <a name="debug">Debugging Information</a>
+</div>
+<!-- *********************************************************************** -->
+
+<div class="doc_text">
+
+<p><tt> ... To be completed ... </tt></p>
+
+</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>
+ <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>
+ <a href="http://llvm.org">LLVM Compiler Infrastructure</a><br>
+ Last modified: $Date$
+</address>
+
+</body>
+</html>