docs/LinkTimeOptimization.html

   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">
  10   LLVM Link Time Optimization: design and implementation
  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>
  20   <li><a href="#multiphase">Multi-phase communication between LLVM and linker</a>
  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>
  27   <li><a href="#lto">LLVMlto</a>
  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>
  32   </ul></li>
  33   <li><a href="#debug">Debugging Information</a></li>
  34 </ul>
  35
  36 <div class="doc_author">
  37 <p>Written by Devang Patel</p>
  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>
  48 LLVM features powerful intermodular optimization which can be used at link time.
  49 Link Time Optimization is another name of intermodular optimization when it
  50 is done during link stage. This document describes the interface between LLVM
  51 intermodular 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>
  63 The LLVM Link Time Optimizer seeks complete transparency, while doing intermodular
  64 optimization, in compiler tool chain. Its main goal is to let developer take
  65 advantage of intermodular optimizer without making any significant changes to
  66 their makefiles or build system. This is achieved through tight integration with
  67 linker. In this model, linker treates LLVM bytecode files like native objects
  68 file and allows mixing and matching among them. The linker uses
  69 <a href="#lto">LLVMlto</a>, a dynamically loaded library, to handle LLVM bytecode
  70 files. This tight integration between the linker and LLVM optimizer helps to do
  71 optimizations that are not possible in other models. The linker input allows
  72 optimizer to avoid relying on conservative escape analysis.
  73 </p>
  74 </div>
  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
  84 clean interface.
  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 <code>
  90 --- a.h ---
  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 ---
 118 <br>#include &lt;stdio.h&gt;
 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>
 135 <p>
 136 In this example, the linker recognizes that <tt>foo2()</tt> is a externally visible
 137 symbol defined in LLVM byte code file. This information is collected using
 138 <a href="#readllvmobjectfile"> readLLVMObjectFile() </a>. Based on this
 139 information, 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
 141 and it removes <tt>foo2()</tt>. As soon as <tt>foo2()</tt> is removed, optimizer
 142 recognizes 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.
 144 And this in turn, enables linker to remove <tt>foo4()</tt>.
 145 This example illustrates advantage of tight integration with linker. Here,
 146 optimizer 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>
 157 <ul>
 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
 160 collected during normal linker's symbol resolution phase. In above example,
 161 optimizer can not remove <tt>foo2()</tt> without linker's input because it is
 162 externally 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
 166 capabilities to collect information for link time optimizer. Not only such code
 167 duplication is difficult to justify but it also has several other disadvantages.
 168 For example, the linking semantics and the features provided by linker on
 169 various platform are not unique. This means, this new tool needs to support all
 170 such features and platforms in one super tool or one new separate tool per
 171 platform is required. This increases maintance cost for link time optimizer
 172 significantly, which is not necessary. Plus, this approach requires staying
 173 synchronized with linker developements on various platforms, which is not the
 174 main focus of link time optimizer. Finally, this approach increases end user's build
 175 time due to duplicate work done by this separate tool and linker itself.
 176 </ul>
 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>
 186 The linker collects information about symbol defininitions and uses in various
 187 link objects which is more accurate than any information collected by other tools
 188 during typical build cycle.
 189 The linker collects this information by looking at definitions and uses of
 190 symbols in native .o files and using symbol visibility information. The linker
 191 also uses user supplied information, such as list of exported symbol.
 192 LLVM optimizer collects control flow information, data flow information and
 193 knows much more about program structure from optimizer's point of view. Our
 194 goal is to take advantage of tight intergration between the linker and
 195 optimizer 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>
 206 The linker first reads all object files in natural order and collects symbol
 207 information. This includes native object files as well as LLVM byte code files.
 208 In this phase, the linker uses <a href="#readllvmobjectfile"> readLLVMObjectFile() </a>
 209 to collect symbol  information from each LLVM bytecode files and updates its
 210 internal global symbol table accordingly. The intent of this interface is to
 211 avoid overhead in the non LLVM case, where all input object files are native
 212 object files, by putting this code in the error path of the linker. When the
 213 linker sees the first llvm .o file, it dlopen()s the dynamic library. This is
 214 to 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>
 225 In this stage, the linker resolves symbols using global symbol table information
 226 to report undefined symbol errors, read archive members, resolve weak
 227 symbols etc... The linker is able to do this seamlessly even though it does not
 228 know exact content of input LLVM bytecode files because it uses symbol information
 229 provided by <a href="#readllvmobjectfile"> readLLVMObjectFile() </a>.
 230 If 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>
 240 After symbol resolution, the linker updates symbol information supplied by LLVM
 241 bytecode files appropriately. For example, whether certain LLVM bytecode
 242 supplied symbols are used or not. In the example above, the linker reports
 243 that <tt>foo2()</tt> is not used anywhere in the program, including native .o
 244 files. This information is used by LLVM interprocedural optimizer. The
 245 linker uses <a href="#optimizemodules"> optimizeModules()</a> and requests
 246 optimized 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>
 257 In this phase, the linker reads optimized native object file and updates internal
 258 global symbol table to reflect any changes. Linker also collects information
 259 about any change in use of external symbols by LLVM bytecode files. In the examle
 260 above, the linker notes that <tt>foo4()</tt> is not used any more. If dead code
 261 striping is enabled then linker refreshes live symbol information appropriately
 262 and performs dead code stripping.
 263 <br>
 264 After this phase, the linker continues linking as if it never saw LLVM bytecode
 265 files.
 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
 277 intended for use by a linker. <tt>LLVMlto</tt> provides an abstract C++ interface
 278 to use the LLVM interprocedural optimizer without exposing details of LLVM
 279 internals. The intention is to keep the interface as stable as possible even
 280 when 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
 292 and global variables, tdefined in LLVM bytecode files, to linker.
 293 This includes symbol visibility information. This information is used by linker
 294 to do symbol resolution. For example : function <tt>foo2()</tt> is defined inside
 295 a LLVM bytecode module and it is externally visible symbol.
 296 This helps linker connect use of <tt>foo2()</tt> in native object file with
 297 future definition of symbol <tt>foo2()</tt>. The linker will see actual definition
 298 of <tt>foo2()</tt> when it receives optimized native object file in <a href="#phase4">
 299 Symbol Resolution after optimization</a> phase. If the linker does not find any
 300 use of <tt>foo2()</tt>, it updates LLVMSymbol visibility information to notify
 301 LLVM intermodular optimizer that it is dead. The LLVM intermodular optimizer
 302 takes 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
 314 and collect LLVMSymbol nformation. This routine also
 315 supplies list of externally defined symbols that are used by LLVM bytecode
 316 files. Linker uses this symbol information to do symbol  resolution. Internally,
 317 <a href="#lto">LLVMlto</a> maintains LLVM bytecode modules in memory. This
 318 function 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>
 329 The linker invokes <tt>optimizeModules</tt> to optimize already read LLVM
 330 bytecode files by applying LLVM intermodular optimization techniques. This
 331 function runs LLVM intermodular optimizer and generates native object code
 332 as .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
 357   Devang Patel<br>
 358   <a href="http://llvm.org">LLVM Compiler Infrastructure</a><br>
 359   Last modified: $Date$
 360 </address>
 361
 362 </body>
 363 </html>