Gitiles
Code Review Sign In
gerrit-public.fairphone.software / fp2-dev / platform / external / llvm / e6dd6a11d172d2efb11ccbe2b1264244b6f02a1b / . / docs / LinkTimeOptimization.html
blob: 019ba7574dc244907aecff79fc89431483f5ea7a [file] [log] [blame]
Devang Patel93449f12006-08-14 18:03:40 +0000[diff] [blame]1<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
2 "http://www.w3.org/TR/html4/strict.dtd">
3<html>
4<head>
5 <title>LLVM Link Time Optimization: design and implementation</title>
6 <link rel="stylesheet" href="llvm.css" type="text/css">
7</head>
8
9<div class="doc_title">
Devang Patel2c1292f2006-08-14 18:39:35 +0000[diff] [blame]10 LLVM Link Time Optimization: design and implementation
Devang Patel93449f12006-08-14 18:03:40 +0000[diff] [blame]11</div>
12
13<ul>
14 <li><a href="#desc">Description</a></li>
15 <li><a href="#design">Design Philosophy</a>
16 <ul>
17 <li><a href="#example1">Example of link time optimization</a></li>
18 <li><a href="#alternative_approaches">Alternative Approaches</a></li>
19 </ul></li>
Devang Patel2c1292f2006-08-14 18:39:35 +0000[diff] [blame]20 <li><a href="#multiphase">Multi-phase communication between LLVM and linker</a>
Devang Patel93449f12006-08-14 18:03:40 +0000[diff] [blame]21 <ul>
22 <li><a href="#phase1">Phase 1 : Read LLVM Bytecode Files</a></li>
23 <li><a href="#phase2">Phase 2 : Symbol Resolution</a></li>
24 <li><a href="#phase3">Phase 3 : Optimize Bytecode Files</a></li>
25 <li><a href="#phase4">Phase 4 : Symbol Resolution after optimization</a></li>
26 </ul></li>
Devang Patel2c1292f2006-08-14 18:39:35 +0000[diff] [blame]27 <li><a href="#lto">LLVMlto</a>
Devang Patel93449f12006-08-14 18:03:40 +0000[diff] [blame]28 <ul>
29 <li><a href="#llvmsymbol">LLVMSymbol</a></li>
30 <li><a href="#readllvmobjectfile">readLLVMObjectFile()</a></li>
31 <li><a href="#optimizemodules">optimizeModules()</a></li>
Devang Patel2c1292f2006-08-14 18:39:35 +0000[diff] [blame]32 </ul></li>
Devang Patel93449f12006-08-14 18:03:40 +0000[diff] [blame]33 <li><a href="#debug">Debugging Information</a></li>
34</ul>
35
36<div class="doc_author">
Devang Patel2c1292f2006-08-14 18:39:35 +0000[diff] [blame]37<p>Written by Devang Patel</p>
Devang Patel93449f12006-08-14 18:03:40 +0000[diff] [blame]38</div>
39
40<!-- *********************************************************************** -->
41<div class="doc_section">
42<a name="desc">Description</a>
43</div>
44<!-- *********************************************************************** -->
45
46<div class="doc_text">
47<p>
48LLVM features powerful intermodular optimization which can be used at link time.
49Link Time Optimization is another name of intermodular optimization when it
50is done during link stage. This document describes the interface between LLVM
51intermodular optimizer and the linker and its design.
52</p>
53</div>
54
55<!-- *********************************************************************** -->
56<div class="doc_section">
57<a name="design">Design Philosophy</a>
58</div>
59<!-- *********************************************************************** -->
60
61<div class="doc_text">
62<p>
63The LLVM Link Time Optimizer seeks complete transparency, while doing intermodular
64optimization, in compiler tool chain. Its main goal is to let developer take
65advantage of intermodular optimizer without making any significant changes to
66their makefiles or build system. This is achieved through tight integration with
67linker. In this model, linker treates LLVM bytecode files like native objects
68file and allows mixing and matching among them. The linker uses
69<a href="#lto">LLVMlto</a>, a dynamically loaded library, to handle LLVM bytecode
70files. This tight integration between the linker and LLVM optimizer helps to do
71optimizations that are not possible in other models. The linker input allows
72optimizer to avoid relying on conservative escape analysis.
73</p>
Devang Patel2c1292f2006-08-14 18:39:35 +0000[diff] [blame]74</div>
Devang Patel93449f12006-08-14 18:03:40 +0000[diff] [blame]75
76<!-- ======================================================================= -->
77<div class="doc_subsection">
78 <a name="example1">Example of link time optimization</a>
79</div>
80
81<div class="doc_text">
82
83<p>Following example illustrates advantage of integrated approach that uses
84clean interface.
Devang Patel2c1292f2006-08-14 18:39:35 +0000[diff] [blame]85<ul>
Devang Patel93449f12006-08-14 18:03:40 +0000[diff] [blame]86<li> Input source file <tt>a.c</tt> is compiled into LLVM byte code form.
87<li> Input source file <tt>main.c</tt> is compiled into native object code.
Devang Patel2c1292f2006-08-14 18:39:35 +0000[diff] [blame]88</ul>
Devang Patel93449f12006-08-14 18:03:40 +0000[diff] [blame]89<code>
Devang Patel2c1292f2006-08-14 18:39:35 +0000[diff] [blame]90--- a.h ---
Devang Patel93449f12006-08-14 18:03:40 +0000[diff] [blame]91<br>extern int foo1(void);
92<br>extern void foo2(void);
93<br>extern void foo4(void);
94<br>--- a.c ---
95<br>#include "a.h"
96<br>
97<br>static signed int i = 0;
98<br>
99<br>void foo2(void) {
100<br> i = -1;
101<br>}
102<br>
103<br>static int foo3() {
104<br>foo4();
105<br>return 10;
106<br>}
107<br>
108<br>int foo1(void) {
109<br>int data = 0;
110<br>
111<br>if (i < 0) { data = foo3(); }
112<br>
113<br>data = data + 42;
114<br>return data;
115<br>}
116<br>
117<br>--- main.c ---
Devang Patele6dd6a12006-08-14 18:49:03 +0000[diff] [blame^]118<br>#include &lt;stdio.h&gt;
Devang Patel93449f12006-08-14 18:03:40 +0000[diff] [blame]119<br>#include "a.h"
120<br>
121<br>void foo4(void) {
122<br> printf ("Hi\n");
123<br>}
124<br>
125<br>int main() {
126<br> return foo1();
127<br>}
128<br>
129<br>--- command lines ---
130<br> $ llvm-gcc4 --emit-llvm -c a.c -o a.o # <-- a.o is LLVM bytecode file
131<br> $ llvm-gcc4 -c main.c -o main.o # <-- main.o is native object file
132<br> $ llvm-gcc4 a.o main.o -o main # <-- standard link command without any modifications
133<br>
134</code>
Devang Patel93449f12006-08-14 18:03:40 +0000[diff] [blame]135<p>
136In this example, the linker recognizes that <tt>foo2()</tt> is a externally visible
137symbol defined in LLVM byte code file. This information is collected using
Devang Patel2c1292f2006-08-14 18:39:35 +0000[diff] [blame]138<a href="#readllvmobjectfile"> readLLVMObjectFile() </a>. Based on this
Devang Patel93449f12006-08-14 18:03:40 +0000[diff] [blame]139information, linker completes its usual symbol resolution pass and finds that
140<tt>foo2()</tt> is not used anywhere. This information is used by LLVM optimizer
141and it removes <tt>foo2()</tt>. As soon as <tt>foo2()</tt> is removed, optimizer
142recognizes that condition <tt> i < 0 </tt> is always false, which means
143<tt>foo3()</tt> is never used. Hence, optimizer removes <tt>foo3()</tt> also.
144And this in turn, enables linker to remove <tt>foo4()</tt>.
145This example illustrates advantage of tight integration with linker. Here,
146optimizer can not remove <tt>foo3()</tt> without the linker's input.
147</p>
148</div>
149
150<!-- ======================================================================= -->
151<div class="doc_subsection">
152 <a name="alternative_approaches">Alternative Approaches</a>
153</div>
154
155<div class="doc_text">
156<p>
Devang Patel2c1292f2006-08-14 18:39:35 +0000[diff] [blame]157<ul>
Devang Patel93449f12006-08-14 18:03:40 +0000[diff] [blame]158<li> Compiler driver invokes link time optimizer separately.
159<br><br>In this model link time optimizer is not able to take advantage of information
160collected during normal linker's symbol resolution phase. In above example,
161optimizer can not remove <tt>foo2()</tt> without linker's input because it is
162externally visible. And this in turn prohibits optimizer from removing <tt>foo3()</tt>.
163<br><br>
164<li> Use separate tool to collect symbol information from all object file.
165<br><br>In this model, this new separate tool or library replicates linker's
166capabilities to collect information for link time optimizer. Not only such code
167duplication is difficult to justify but it also has several other disadvantages.
168For example, the linking semantics and the features provided by linker on
169various platform are not unique. This means, this new tool needs to support all
170such features and platforms in one super tool or one new separate tool per
171platform is required. This increases maintance cost for link time optimizer
172significantly, which is not necessary. Plus, this approach requires staying
173synchronized with linker developements on various platforms, which is not the
174main focus of link time optimizer. Finally, this approach increases end user's build
175time due to duplicate work done by this separate tool and linker itself.
Devang Patel2c1292f2006-08-14 18:39:35 +0000[diff] [blame]176</ul>
Devang Patel93449f12006-08-14 18:03:40 +0000[diff] [blame]177</div>
178
179<!-- *********************************************************************** -->
180<div class="doc_section">
181 <a name="multiphase">Multi-phase communication between LLVM and linker</a>
182</div>
183
184<div class="doc_text">
185<p>
186The linker collects information about symbol defininitions and uses in various
187link objects which is more accurate than any information collected by other tools
188during typical build cycle.
189The linker collects this information by looking at definitions and uses of
190symbols in native .o files and using symbol visibility information. The linker
191also uses user supplied information, such as list of exported symbol.
192LLVM optimizer collects control flow information, data flow information and
193knows much more about program structure from optimizer's point of view. Our
194goal is to take advantage of tight intergration between the linker and
195optimizer by sharing this information during various linking phases.
196</p>
197</div>
198
199<!-- ======================================================================= -->
200<div class="doc_subsection">
201 <a name="phase1">Phase 1 : Read LLVM Bytecode Files</a>
202</div>
203
204<div class="doc_text">
205<p>
206The linker first reads all object files in natural order and collects symbol
207information. This includes native object files as well as LLVM byte code files.
Devang Patel2c1292f2006-08-14 18:39:35 +0000[diff] [blame]208In this phase, the linker uses <a href="#readllvmobjectfile"> readLLVMObjectFile() </a>
Devang Patel93449f12006-08-14 18:03:40 +0000[diff] [blame]209to collect symbol information from each LLVM bytecode files and updates its
210internal global symbol table accordingly. The intent of this interface is to
211avoid overhead in the non LLVM case, where all input object files are native
212object files, by putting this code in the error path of the linker. When the
213linker sees the first llvm .o file, it dlopen()s the dynamic library. This is
214to allow changes to LLVM part without relinking the linker.
215</p>
216</div>
217
218<!-- ======================================================================= -->
219<div class="doc_subsection">
220 <a name="phase2">Phase 2 : Symbol Resolution</a>
221</div>
222
223<div class="doc_text">
224<p>
225In this stage, the linker resolves symbols using global symbol table information
226to report undefined symbol errors, read archive members, resolve weak
227symbols etc... The linker is able to do this seamlessly even though it does not
228know exact content of input LLVM bytecode files because it uses symbol information
Devang Patel2c1292f2006-08-14 18:39:35 +0000[diff] [blame]229provided by <a href="#readllvmobjectfile"> readLLVMObjectFile() </a>.
Devang Patel93449f12006-08-14 18:03:40 +0000[diff] [blame]230If dead code stripping is enabled then linker collects list of live symbols.
231</p>
232</div>
233
234<!-- ======================================================================= -->
235<div class="doc_subsection">
236 <a name="phase3">Phase 3 : Optimize Bytecode Files</a>
237</div>
238<div class="doc_text">
239<p>
240After symbol resolution, the linker updates symbol information supplied by LLVM
241bytecode files appropriately. For example, whether certain LLVM bytecode
242supplied symbols are used or not. In the example above, the linker reports
243that <tt>foo2()</tt> is not used anywhere in the program, including native .o
244files. This information is used by LLVM interprocedural optimizer. The
245linker uses <a href="#optimizemodules"> optimizeModules()</a> and requests
246optimized native object file of the LLVM portion of the program.
247</p>
248</div>
249
250<!-- ======================================================================= -->
251<div class="doc_subsection">
252 <a name="phase4">Phase 4 : Symbol Resolution after optimization</a>
253</div>
254
255<div class="doc_text">
256<p>
257In this phase, the linker reads optimized native object file and updates internal
258global symbol table to reflect any changes. Linker also collects information
259about any change in use of external symbols by LLVM bytecode files. In the examle
260above, the linker notes that <tt>foo4()</tt> is not used any more. If dead code
261striping is enabled then linker refreshes live symbol information appropriately
262and performs dead code stripping.
263<br>
264After this phase, the linker continues linking as if it never saw LLVM bytecode
265files.
266</p>
267</div>
268
269<!-- *********************************************************************** -->
270<div class="doc_section">
271<a name="lto">LLVMlto</a>
272</div>
273
274<div class="doc_text">
275<p>
276<tt>LLVMlto</tt> is a dynamic library that is part of the LLVM tools, and is
277intended for use by a linker. <tt>LLVMlto</tt> provides an abstract C++ interface
278to use the LLVM interprocedural optimizer without exposing details of LLVM
279internals. The intention is to keep the interface as stable as possible even
280when the LLVM optimizer continues to evolve.
281</p>
282</div>
283
284<!-- ======================================================================= -->
285<div class="doc_subsection">
286 <a name="llvmsymbol">LLVMSymbol</a>
287</div>
288
289<div class="doc_text">
290<p>
291<tt>LLVMSymbol</tt> class is used to describe the externally visible functions
292and global variables, tdefined in LLVM bytecode files, to linker.
293This includes symbol visibility information. This information is used by linker
294to do symbol resolution. For example : function <tt>foo2()</tt> is defined inside
295a LLVM bytecode module and it is externally visible symbol.
296This helps linker connect use of <tt>foo2()</tt> in native object file with
297future definition of symbol <tt>foo2()</tt>. The linker will see actual definition
298of <tt>foo2()</tt> when it receives optimized native object file in <a href="#phase4">
299Symbol Resolution after optimization</a> phase. If the linker does not find any
300use of <tt>foo2()</tt>, it updates LLVMSymbol visibility information to notify
301LLVM intermodular optimizer that it is dead. The LLVM intermodular optimizer
302takes advantage of such information to generate better code.
303</p>
304</div>
305
306<!-- ======================================================================= -->
307<div class="doc_subsection">
308 <a name="readllvmobjectfile">readLLVMObjectFile()</a>
309</div>
310
311<div class="doc_text">
312<p>
313<tt>readLLVMObjectFile()</tt> is used by the linker to read LLVM bytecode files
314and collect LLVMSymbol nformation. This routine also
315supplies list of externally defined symbols that are used by LLVM bytecode
316files. Linker uses this symbol information to do symbol resolution. Internally,
317<a href="#lto">LLVMlto</a> maintains LLVM bytecode modules in memory. This
318function also provides list of external references used by bytecode file.<br>
319</p>
320</div>
321
322<!-- ======================================================================= -->
323<div class="doc_subsection">
324 <a name="optimizemodules">optimizeModules()</a>
325</div>
326
327<div class="doc_text">
328<p>
329The linker invokes <tt>optimizeModules</tt> to optimize already read LLVM
330bytecode files by applying LLVM intermodular optimization techniques. This
331function runs LLVM intermodular optimizer and generates native object code
332as .o file at name and location provided by the linker.
333</p>
334</div>
335
336<!-- *********************************************************************** -->
337<div class="doc_section">
338 <a name="debug">Debugging Information</a>
339</div>
340<!-- *********************************************************************** -->
341
342<div class="doc_text">
343
344<p><tt> ... incomplete ... </tt></p>
345
346</div>
347
348<!-- *********************************************************************** -->
349
350<hr>
351<address>
352 <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
353 src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
354 <a href="http://validator.w3.org/check/referer"><img
355 src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
356
Devang Patel2c1292f2006-08-14 18:39:35 +0000[diff] [blame]357 Devang Patel<br>
Devang Patel93449f12006-08-14 18:03:40 +0000[diff] [blame]358 <a href="http://llvm.org">LLVM Compiler Infrastructure</a><br>
359 Last modified: $Date$
360</address>
361
362</body>
363</html>