LTO-Overview.html 9.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210
  1. <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
  2. <html>
  3. <!-- Copyright (C) 1988-2017 Free Software Foundation, Inc.
  4. Permission is granted to copy, distribute and/or modify this document
  5. under the terms of the GNU Free Documentation License, Version 1.3 or
  6. any later version published by the Free Software Foundation; with the
  7. Invariant Sections being "Funding Free Software", the Front-Cover
  8. Texts being (a) (see below), and with the Back-Cover Texts being (b)
  9. (see below). A copy of the license is included in the section entitled
  10. "GNU Free Documentation License".
  11. (a) The FSF's Front-Cover Text is:
  12. A GNU Manual
  13. (b) The FSF's Back-Cover Text is:
  14. You have freedom to copy and modify this GNU Manual, like GNU
  15. software. Copies published by the Free Software Foundation raise
  16. funds for GNU development. -->
  17. <!-- Created by GNU Texinfo 5.2, http://www.gnu.org/software/texinfo/ -->
  18. <head>
  19. <title>GNU Compiler Collection (GCC) Internals: LTO Overview</title>
  20. <meta name="description" content="GNU Compiler Collection (GCC) Internals: LTO Overview">
  21. <meta name="keywords" content="GNU Compiler Collection (GCC) Internals: LTO Overview">
  22. <meta name="resource-type" content="document">
  23. <meta name="distribution" content="global">
  24. <meta name="Generator" content="makeinfo">
  25. <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
  26. <link href="index.html#Top" rel="start" title="Top">
  27. <link href="Option-Index.html#Option-Index" rel="index" title="Option Index">
  28. <link href="index.html#SEC_Contents" rel="contents" title="Table of Contents">
  29. <link href="LTO.html#LTO" rel="up" title="LTO">
  30. <link href="LTO-object-file-layout.html#LTO-object-file-layout" rel="next" title="LTO object file layout">
  31. <link href="LTO.html#LTO" rel="prev" title="LTO">
  32. <style type="text/css">
  33. <!--
  34. a.summary-letter {text-decoration: none}
  35. blockquote.smallquotation {font-size: smaller}
  36. div.display {margin-left: 3.2em}
  37. div.example {margin-left: 3.2em}
  38. div.indentedblock {margin-left: 3.2em}
  39. div.lisp {margin-left: 3.2em}
  40. div.smalldisplay {margin-left: 3.2em}
  41. div.smallexample {margin-left: 3.2em}
  42. div.smallindentedblock {margin-left: 3.2em; font-size: smaller}
  43. div.smalllisp {margin-left: 3.2em}
  44. kbd {font-style:oblique}
  45. pre.display {font-family: inherit}
  46. pre.format {font-family: inherit}
  47. pre.menu-comment {font-family: serif}
  48. pre.menu-preformatted {font-family: serif}
  49. pre.smalldisplay {font-family: inherit; font-size: smaller}
  50. pre.smallexample {font-size: smaller}
  51. pre.smallformat {font-family: inherit; font-size: smaller}
  52. pre.smalllisp {font-size: smaller}
  53. span.nocodebreak {white-space:nowrap}
  54. span.nolinebreak {white-space:nowrap}
  55. span.roman {font-family:serif; font-weight:normal}
  56. span.sansserif {font-family:sans-serif; font-weight:normal}
  57. ul.no-bullet {list-style: none}
  58. -->
  59. </style>
  60. </head>
  61. <body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000">
  62. <a name="LTO-Overview"></a>
  63. <div class="header">
  64. <p>
  65. Next: <a href="LTO-object-file-layout.html#LTO-object-file-layout" accesskey="n" rel="next">LTO object file layout</a>, Up: <a href="LTO.html#LTO" accesskey="u" rel="up">LTO</a> &nbsp; [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Option-Index.html#Option-Index" title="Index" rel="index">Index</a>]</p>
  66. </div>
  67. <hr>
  68. <a name="Design-Overview"></a>
  69. <h3 class="section">24.1 Design Overview</h3>
  70. <p>Link time optimization is implemented as a GCC front end for a
  71. bytecode representation of GIMPLE that is emitted in special sections
  72. of <code>.o</code> files. Currently, LTO support is enabled in most
  73. ELF-based systems, as well as darwin, cygwin and mingw systems.
  74. </p>
  75. <p>Since GIMPLE bytecode is saved alongside final object code, object
  76. files generated with LTO support are larger than regular object files.
  77. This &ldquo;fat&rdquo; object format makes it easy to integrate LTO into
  78. existing build systems, as one can, for instance, produce archives of
  79. the files. Additionally, one might be able to ship one set of fat
  80. objects which could be used both for development and the production of
  81. optimized builds. A, perhaps surprising, side effect of this feature
  82. is that any mistake in the toolchain leads to LTO information not
  83. being used (e.g. an older <code>libtool</code> calling <code>ld</code> directly).
  84. This is both an advantage, as the system is more robust, and a
  85. disadvantage, as the user is not informed that the optimization has
  86. been disabled.
  87. </p>
  88. <p>The current implementation only produces &ldquo;fat&rdquo; objects, effectively
  89. doubling compilation time and increasing file sizes up to 5x the
  90. original size. This hides the problem that some tools, such as
  91. <code>ar</code> and <code>nm</code>, need to understand symbol tables of LTO
  92. sections. These tools were extended to use the plugin infrastructure,
  93. and with these problems solved, GCC will also support &ldquo;slim&rdquo; objects
  94. consisting of the intermediate code alone.
  95. </p>
  96. <p>At the highest level, LTO splits the compiler in two. The first half
  97. (the &ldquo;writer&rdquo;) produces a streaming representation of all the
  98. internal data structures needed to optimize and generate code. This
  99. includes declarations, types, the callgraph and the GIMPLE representation
  100. of function bodies.
  101. </p>
  102. <p>When <samp>-flto</samp> is given during compilation of a source file, the
  103. pass manager executes all the passes in <code>all_lto_gen_passes</code>.
  104. Currently, this phase is composed of two IPA passes:
  105. </p>
  106. <ul>
  107. <li> <code>pass_ipa_lto_gimple_out</code>
  108. This pass executes the function <code>lto_output</code> in
  109. <samp>lto-streamer-out.c</samp>, which traverses the call graph encoding
  110. every reachable declaration, type and function. This generates a
  111. memory representation of all the file sections described below.
  112. </li><li> <code>pass_ipa_lto_finish_out</code>
  113. This pass executes the function <code>produce_asm_for_decls</code> in
  114. <samp>lto-streamer-out.c</samp>, which takes the memory image built in the
  115. previous pass and encodes it in the corresponding ELF file sections.
  116. </li></ul>
  117. <p>The second half of LTO support is the &ldquo;reader&rdquo;. This is implemented
  118. as the GCC front end <samp>lto1</samp> in <samp>lto/lto.c</samp>. When
  119. <samp>collect2</samp> detects a link set of <code>.o</code>/<code>.a</code> files with
  120. LTO information and the <samp>-flto</samp> is enabled, it invokes
  121. <samp>lto1</samp> which reads the set of files and aggregates them into a
  122. single translation unit for optimization. The main entry point for
  123. the reader is <samp>lto/lto.c</samp>:<code>lto_main</code>.
  124. </p>
  125. <a name="LTO-modes-of-operation"></a>
  126. <h4 class="subsection">24.1.1 LTO modes of operation</h4>
  127. <p>One of the main goals of the GCC link-time infrastructure was to allow
  128. effective compilation of large programs. For this reason GCC implements two
  129. link-time compilation modes.
  130. </p>
  131. <ol>
  132. <li> <em>LTO mode</em>, in which the whole program is read into the
  133. compiler at link-time and optimized in a similar way as if it
  134. were a single source-level compilation unit.
  135. </li><li> <em>WHOPR or partitioned mode</em>, designed to utilize multiple
  136. CPUs and/or a distributed compilation environment to quickly link
  137. large applications. WHOPR stands for WHOle Program optimizeR (not to
  138. be confused with the semantics of <samp>-fwhole-program</samp>). It
  139. partitions the aggregated callgraph from many different <code>.o</code>
  140. files and distributes the compilation of the sub-graphs to different
  141. CPUs.
  142. <p>Note that distributed compilation is not implemented yet, but since
  143. the parallelism is facilitated via generating a <code>Makefile</code>, it
  144. would be easy to implement.
  145. </p></li></ol>
  146. <p>WHOPR splits LTO into three main stages:
  147. </p><ol>
  148. <li> Local generation (LGEN)
  149. This stage executes in parallel. Every file in the program is compiled
  150. into the intermediate language and packaged together with the local
  151. call-graph and summary information. This stage is the same for both
  152. the LTO and WHOPR compilation mode.
  153. </li><li> Whole Program Analysis (WPA)
  154. WPA is performed sequentially. The global call-graph is generated, and
  155. a global analysis procedure makes transformation decisions. The global
  156. call-graph is partitioned to facilitate parallel optimization during
  157. phase 3. The results of the WPA stage are stored into new object files
  158. which contain the partitions of program expressed in the intermediate
  159. language and the optimization decisions.
  160. </li><li> Local transformations (LTRANS)
  161. This stage executes in parallel. All the decisions made during phase 2
  162. are implemented locally in each partitioned object file, and the final
  163. object code is generated. Optimizations which cannot be decided
  164. efficiently during the phase 2 may be performed on the local
  165. call-graph partitions.
  166. </li></ol>
  167. <p>WHOPR can be seen as an extension of the usual LTO mode of
  168. compilation. In LTO, WPA and LTRANS are executed within a single
  169. execution of the compiler, after the whole program has been read into
  170. memory.
  171. </p>
  172. <p>When compiling in WHOPR mode, the callgraph is partitioned during
  173. the WPA stage. The whole program is split into a given number of
  174. partitions of roughly the same size. The compiler tries to
  175. minimize the number of references which cross partition boundaries.
  176. The main advantage of WHOPR is to allow the parallel execution of
  177. LTRANS stages, which are the most time-consuming part of the
  178. compilation process. Additionally, it avoids the need to load the
  179. whole program into memory.
  180. </p>
  181. <hr>
  182. <div class="header">
  183. <p>
  184. Next: <a href="LTO-object-file-layout.html#LTO-object-file-layout" accesskey="n" rel="next">LTO object file layout</a>, Up: <a href="LTO.html#LTO" accesskey="u" rel="up">LTO</a> &nbsp; [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Option-Index.html#Option-Index" title="Index" rel="index">Index</a>]</p>
  185. </div>
  186. </body>
  187. </html>