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