--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/gcc/doc/lto.texi	Sun Aug 21 07:07:55 2011 +0900
@@ -0,0 +1,568 @@
+@c Copyright (c) 2010 Free Software Foundation, Inc.
+@c Free Software Foundation, Inc.
+@c This is part of the GCC manual.
+@c For copying conditions, see the file gcc.texi.
+@c Contributed by Jan Hubicka <jh@suse.cz> and
+@c Diego Novillo <dnovillo@google.com>
+
+@node LTO
+@chapter Link Time Optimization
+@cindex lto
+@cindex whopr
+@cindex wpa
+@cindex ltrans
+
+@section Design Overview
+
+Link time optimization is implemented as a GCC front end for a
+bytecode representation of GIMPLE that is emitted in special sections
+of @code{.o} files.  Currently, LTO support is enabled in most
+ELF-based systems, as well as darwin, cygwin and mingw systems.
+
+Since GIMPLE bytecode is saved alongside final object code, object
+files generated with LTO support are larger than regular object files.
+This ``fat'' object format makes it easy to integrate LTO into
+existing build systems, as one can, for instance, produce archives of
+the files.  Additionally, one might be able to ship one set of fat
+objects which could be used both for development and the production of
+optimized builds.  A, perhaps surprising, side effect of this feature
+is that any mistake in the toolchain that leads to LTO information not
+being used (e.g.@: an older @code{libtool} calling @code{ld} directly).
+This is both an advantage, as the system is more robust, and a
+disadvantage, as the user is not informed that the optimization has
+been disabled.
+
+The current implementation only produces ``fat'' objects, effectively
+doubling compilation time and increasing file sizes up to 5x the
+original size.  This hides the problem that some tools, such as
+@code{ar} and @code{nm}, need to understand symbol tables of LTO
+sections.  These tools were extended to use the plugin infrastructure,
+and with these problems solved, GCC will also support ``slim'' objects
+consisting of the intermediate code alone.
+
+At the highest level, LTO splits the compiler in two.  The first half
+(the ``writer'') produces a streaming representation of all the
+internal data structures needed to optimize and generate code.  This
+includes declarations, types, the callgraph and the GIMPLE representation
+of function bodies.
+
+When @option{-flto} is given during compilation of a source file, the
+pass manager executes all the passes in @code{all_lto_gen_passes}.
+Currently, this phase is composed of two IPA passes:
+
+@itemize @bullet
+@item @code{pass_ipa_lto_gimple_out}
+This pass executes the function @code{lto_output} in
+@file{lto-streamer-out.c}, which traverses the call graph encoding
+every reachable declaration, type and function.  This generates a
+memory representation of all the file sections described below.
+
+@item @code{pass_ipa_lto_finish_out}
+This pass executes the function @code{produce_asm_for_decls} in
+@file{lto-streamer-out.c}, which takes the memory image built in the
+previous pass and encodes it in the corresponding ELF file sections.
+@end itemize
+
+The second half of LTO support is the ``reader''.  This is implemented
+as the GCC front end @file{lto1} in @file{lto/lto.c}.  When
+@file{collect2} detects a link set of @code{.o}/@code{.a} files with
+LTO information and the @option{-flto} is enabled, it invokes
+@file{lto1} which reads the set of files and aggregates them into a
+single translation unit for optimization.  The main entry point for
+the reader is @file{lto/lto.c}:@code{lto_main}.
+
+@subsection LTO modes of operation
+
+One of the main goals of the GCC link-time infrastructure was to allow
+effective compilation of large programs.  For this reason GCC implements two
+link-time compilation modes.
+
+@enumerate
+@item	@emph{LTO mode}, in which the whole program is read into the
+compiler at link-time and optimized in a similar way as if it
+were a single source-level compilation unit.
+
+@item	@emph{WHOPR or partitioned mode}, designed to utilize multiple
+CPUs and/or a distributed compilation environment to quickly link
+large applications.  WHOPR stands for WHOle Program optimizeR (not to
+be confused with the semantics of @option{-fwhole-program}).  It
+partitions the aggregated callgraph from many different @code{.o}
+files and distributes the compilation of the sub-graphs to different
+CPUs.
+
+Note that distributed compilation is not implemented yet, but since
+the parallelism is facilitated via generating a @code{Makefile}, it
+would be easy to implement.
+@end enumerate
+
+WHOPR splits LTO into three main stages:
+@enumerate
+@item Local generation (LGEN)
+This stage executes in parallel.  Every file in the program is compiled
+into the intermediate language and packaged together with the local
+call-graph and summary information.  This stage is the same for both
+the LTO and WHOPR compilation mode.
+
+@item Whole Program Analysis (WPA)
+WPA is performed sequentially.  The global call-graph is generated, and
+a global analysis procedure makes transformation decisions.  The global
+call-graph is partitioned to facilitate parallel optimization during
+phase 3.  The results of the WPA stage are stored into new object files
+which contain the partitions of program expressed in the intermediate
+language and the optimization decisions.
+
+@item Local transformations (LTRANS)
+This stage executes in parallel.  All the decisions made during phase 2
+are implemented locally in each partitioned object file, and the final
+object code is generated.  Optimizations which cannot be decided
+efficiently during the phase 2 may be performed on the local
+call-graph partitions.
+@end enumerate
+
+WHOPR can be seen as an extension of the usual LTO mode of
+compilation.  In LTO, WPA and LTRANS are executed within a single
+execution of the compiler, after the whole program has been read into
+memory.
+
+When compiling in WHOPR mode, the callgraph is partitioned during
+the WPA stage.  The whole program is split into a given number of
+partitions of roughly the same size.  The compiler tries to
+minimize the number of references which cross partition boundaries.
+The main advantage of WHOPR is to allow the parallel execution of
+LTRANS stages, which are the most time-consuming part of the
+compilation process.  Additionally, it avoids the need to load the
+whole program into memory.
+
+
+@section LTO file sections
+
+LTO information is stored in several ELF sections inside object files.
+Data structures and enum codes for sections are defined in
+@file{lto-streamer.h}.
+
+These sections are emitted from @file{lto-streamer-out.c} and mapped
+in all at once from @file{lto/lto.c}:@code{lto_file_read}.  The
+individual functions dealing with the reading/writing of each section
+are described below.
+
+@itemize @bullet
+@item Command line options (@code{.gnu.lto_.opts})
+
+This section contains the command line options used to generate the
+object files.  This is used at link time to determine the optimization
+level and other settings when they are not explicitly specified at the
+linker command line.
+
+Currently, GCC does not support combining LTO object files compiled
+with different set of the command line options into a single binary.
+At link time, the options given on the command line and the options
+saved on all the files in a link-time set are applied globally.  No
+attempt is made at validating the combination of flags (other than the
+usual validation done by option processing).  This is implemented in
+@file{lto/lto.c}:@code{lto_read_all_file_options}.
+
+
+@item Symbol table (@code{.gnu.lto_.symtab})
+
+This table replaces the ELF symbol table for functions and variables
+represented in the LTO IL.  Symbols used and exported by the optimized
+assembly code of ``fat'' objects might not match the ones used and
+exported by the intermediate code.  This table is necessary because
+the intermediate code is less optimized and thus requires a separate
+symbol table.
+
+Additionally, the binary code in the ``fat'' object will lack a call
+to a function, since the call was optimized out at compilation time
+after the intermediate language was streamed out.  In some special
+cases, the same optimization may not happen during link-time
+optimization.  This would lead to an undefined symbol if only one
+symbol table was used.
+
+The symbol table is emitted in
+@file{lto-streamer-out.c}:@code{produce_symtab}.
+
+
+@item Global declarations and types (@code{.gnu.lto_.decls})
+
+This section contains an intermediate language dump of all
+declarations and types required to represent the callgraph, static
+variables and top-level debug info.
+
+The contents of this section are emitted in
+@file{lto-streamer-out.c}:@code{produce_asm_for_decls}.  Types and
+symbols are emitted in a topological order that preserves the sharing
+of pointers when the file is read back in
+(@file{lto.c}:@code{read_cgraph_and_symbols}).
+
+
+@item The callgraph (@code{.gnu.lto_.cgraph})
+
+This section contains the basic data structure used by the GCC
+inter-procedural optimization infrastructure.  This section stores an
+annotated multi-graph which represents the functions and call sites as
+well as the variables, aliases and top-level @code{asm} statements.
+
+This section is emitted in
+@file{lto-streamer-out.c}:@code{output_cgraph} and read in
+@file{lto-cgraph.c}:@code{input_cgraph}.
+
+
+@item IPA references (@code{.gnu.lto_.refs})
+
+This section contains references between function and static
+variables.  It is emitted by @file{lto-cgraph.c}:@code{output_refs}
+and read by @file{lto-cgraph.c}:@code{input_refs}.
+
+
+@item Function bodies (@code{.gnu.lto_.function_body.<name>})
+
+This section contains function bodies in the intermediate language
+representation.  Every function body is in a separate section to allow
+copying of the section independently to different object files or
+reading the function on demand.
+
+Functions are emitted in
+@file{lto-streamer-out.c}:@code{output_function} and read in
+@file{lto-streamer-in.c}:@code{input_function}.
+
+
+@item Static variable initializers (@code{.gnu.lto_.vars})
+
+This section contains all the symbols in the global variable pool.  It
+is emitted by @file{lto-cgraph.c}:@code{output_varpool} and read in
+@file{lto-cgraph.c}:@code{input_cgraph}.
+
+@item Summaries and optimization summaries used by IPA passes
+(@code{.gnu.lto_.<xxx>}, where @code{<xxx>} is one of @code{jmpfuncs},
+@code{pureconst} or @code{reference})
+
+These sections are used by IPA passes that need to emit summary
+information during LTO generation to be read and aggregated at
+link time.  Each pass is responsible for implementing two pass manager
+hooks: one for writing the summary and another for reading it in.  The
+format of these sections is entirely up to each individual pass.  The
+only requirement is that the writer and reader hooks agree on the
+format.
+@end itemize
+
+
+@section Using summary information in IPA passes
+
+Programs are represented internally as a @emph{callgraph} (a
+multi-graph where nodes are functions and edges are call sites)
+and a @emph{varpool} (a list of static and external variables in
+the program).
+
+The inter-procedural optimization is organized as a sequence of
+individual passes, which operate on the callgraph and the
+varpool.  To make the implementation of WHOPR possible, every
+inter-procedural optimization pass is split into several stages
+that are executed at different times during WHOPR compilation:
+
+@itemize @bullet
+@item LGEN time
+@enumerate
+@item @emph{Generate summary} (@code{generate_summary} in
+@code{struct ipa_opt_pass_d}).  This stage analyzes every function
+body and variable initializer is examined and stores relevant
+information into a pass-specific data structure.
+
+@item @emph{Write summary} (@code{write_summary} in
+@code{struct ipa_opt_pass_d}).  This stage writes all the
+pass-specific information generated by @code{generate_summary}.
+Summaries go into their own @code{LTO_section_*} sections that
+have to be declared in @file{lto-streamer.h}:@code{enum
+lto_section_type}.  A new section is created by calling
+@code{create_output_block} and data can be written using the
+@code{lto_output_*} routines.
+@end enumerate
+
+@item WPA time
+@enumerate
+@item @emph{Read summary} (@code{read_summary} in
+@code{struct ipa_opt_pass_d}).  This stage reads all the
+pass-specific information in exactly the same order that it was
+written by @code{write_summary}.
+
+@item @emph{Execute} (@code{execute} in @code{struct
+opt_pass}).  This performs inter-procedural propagation.  This
+must be done without actual access to the individual function
+bodies or variable initializers.  Typically, this results in a
+transitive closure operation over the summary information of all
+the nodes in the callgraph.
+
+@item @emph{Write optimization summary}
+(@code{write_optimization_summary} in @code{struct
+ipa_opt_pass_d}).  This writes the result of the inter-procedural
+propagation into the object file.  This can use the same data
+structures and helper routines used in @code{write_summary}.
+@end enumerate
+
+@item LTRANS time
+@enumerate
+@item @emph{Read optimization summary}
+(@code{read_optimization_summary} in @code{struct
+ipa_opt_pass_d}).  The counterpart to
+@code{write_optimization_summary}.  This reads the interprocedural
+optimization decisions in exactly the same format emitted by
+@code{write_optimization_summary}.
+
+@item @emph{Transform} (@code{function_transform} and
+@code{variable_transform} in @code{struct ipa_opt_pass_d}).
+The actual function bodies and variable initializers are updated
+based on the information passed down from the @emph{Execute} stage.
+@end enumerate
+@end itemize
+
+The implementation of the inter-procedural passes are shared
+between LTO, WHOPR and classic non-LTO compilation.
+
+@itemize
+@item During the traditional file-by-file mode every pass executes its
+own @emph{Generate summary}, @emph{Execute}, and @emph{Transform}
+stages within the single execution context of the compiler.
+
+@item In LTO compilation mode, every pass uses @emph{Generate
+summary} and @emph{Write summary} stages at compilation time,
+while the @emph{Read summary}, @emph{Execute}, and
+@emph{Transform} stages are executed at link time.
+
+@item In WHOPR mode all stages are used.
+@end itemize
+
+To simplify development, the GCC pass manager differentiates
+between normal inter-procedural passes and small inter-procedural
+passes.  A @emph{small inter-procedural pass}
+(@code{SIMPLE_IPA_PASS}) is a pass that does
+everything at once and thus it can not be executed during WPA in
+WHOPR mode.  It defines only the @emph{Execute} stage and during
+this stage it accesses and modifies the function bodies.  Such
+passes are useful for optimization at LGEN or LTRANS time and are
+used, for example, to implement early optimization before writing
+object files.  The simple inter-procedural passes can also be used
+for easier prototyping and development of a new inter-procedural
+pass.
+
+
+@subsection Virtual clones
+
+One of the main challenges of introducing the WHOPR compilation
+mode was addressing the interactions between optimization passes.
+In LTO compilation mode, the passes are executed in a sequence,
+each of which consists of analysis (or @emph{Generate summary}),
+propagation (or @emph{Execute}) and @emph{Transform} stages.
+Once the work of one pass is finished, the next pass sees the
+updated program representation and can execute.  This makes the
+individual passes dependent on each other.
+
+In WHOPR mode all passes first execute their @emph{Generate
+summary} stage.  Then summary writing marks the end of the LGEN
+stage.  At WPA time,
+the summaries are read back into memory and all passes run the
+@emph{Execute} stage.  Optimization summaries are streamed and
+sent to LTRANS, where all the passes execute the @emph{Transform}
+stage.
+
+Most optimization passes split naturally into analysis,
+propagation and transformation stages.  But some do not.  The
+main problem arises when one pass performs changes and the
+following pass gets confused by seeing different callgraphs
+between the @emph{Transform} stage and the @emph{Generate summary}
+or @emph{Execute} stage.  This means that the passes are required
+to communicate their decisions with each other.
+
+To facilitate this communication, the GCC callgraph
+infrastructure implements @emph{virtual clones}, a method of
+representing the changes performed by the optimization passes in
+the callgraph without needing to update function bodies.
+
+A @emph{virtual clone} in the callgraph is a function that has no
+associated body, just a description of how to create its body based
+on a different function (which itself may be a virtual clone).
+
+The description of function modifications includes adjustments to
+the function's signature (which allows, for example, removing or
+adding function arguments), substitutions to perform on the
+function body, and, for inlined functions, a pointer to the
+function that it will be inlined into.
+
+It is also possible to redirect any edge of the callgraph from a
+function to its virtual clone.  This implies updating of the call
+site to adjust for the new function signature.
+
+Most of the transformations performed by inter-procedural
+optimizations can be represented via virtual clones.  For
+instance, a constant propagation pass can produce a virtual clone
+of the function which replaces one of its arguments by a
+constant.  The inliner can represent its decisions by producing a
+clone of a function whose body will be later integrated into
+a given function.
+
+Using @emph{virtual clones}, the program can be easily updated
+during the @emph{Execute} stage, solving most of pass interactions
+problems that would otherwise occur during @emph{Transform}.
+
+Virtual clones are later materialized in the LTRANS stage and
+turned into real functions.  Passes executed after the virtual
+clone were introduced also perform their @emph{Transform} stage
+on new functions, so for a pass there is no significant
+difference between operating on a real function or a virtual
+clone introduced before its @emph{Execute} stage.
+
+Optimization passes then work on virtual clones introduced before
+their @emph{Execute} stage as if they were real functions.  The
+only difference is that clones are not visible during the
+@emph{Generate Summary} stage.
+
+To keep function summaries updated, the callgraph interface
+allows an optimizer to register a callback that is called every
+time a new clone is introduced as well as when the actual
+function or variable is generated or when a function or variable
+is removed.  These hooks are registered in the @emph{Generate
+summary} stage and allow the pass to keep its information intact
+until the @emph{Execute} stage.  The same hooks can also be
+registered during the @emph{Execute} stage to keep the
+optimization summaries updated for the @emph{Transform} stage.
+
+@subsection IPA references
+
+GCC represents IPA references in the callgraph.  For a function
+or variable @code{A}, the @emph{IPA reference} is a list of all
+locations where the address of @code{A} is taken and, when
+@code{A} is a variable, a list of all direct stores and reads
+to/from @code{A}.  References represent an oriented multi-graph on
+the union of nodes of the callgraph and the varpool.  See
+@file{ipa-reference.c}:@code{ipa_reference_write_optimization_summary}
+and
+@file{ipa-reference.c}:@code{ipa_reference_read_optimization_summary}
+for details.
+
+@subsection Jump functions
+Suppose that an optimization pass sees a function @code{A} and it
+knows the values of (some of) its arguments.  The @emph{jump
+function} describes the value of a parameter of a given function
+call in function @code{A} based on this knowledge.
+
+Jump functions are used by several optimizations, such as the
+inter-procedural constant propagation pass and the
+devirtualization pass.  The inliner also uses jump functions to
+perform inlining of callbacks.
+
+@section Whole program assumptions, linker plugin and symbol visibilities
+
+Link-time optimization gives relatively minor benefits when used
+alone.  The problem is that propagation of inter-procedural
+information does not work well across functions and variables
+that are called or referenced by other compilation units (such as
+from a dynamically linked library).  We say that such functions
+are variables are @emph{externally visible}.
+
+To make the situation even more difficult, many applications
+organize themselves as a set of shared libraries, and the default
+ELF visibility rules allow one to overwrite any externally
+visible symbol with a different symbol at runtime.  This
+basically disables any optimizations across such functions and
+variables, because the compiler cannot be sure that the function
+body it is seeing is the same function body that will be used at
+runtime.  Any function or variable not declared @code{static} in
+the sources degrades the quality of inter-procedural
+optimization.
+
+To avoid this problem the compiler must assume that it sees the
+whole program when doing link-time optimization.  Strictly
+speaking, the whole program is rarely visible even at link-time.
+Standard system libraries are usually linked dynamically or not
+provided with the link-time information.  In GCC, the whole
+program option (@option{-fwhole-program}) asserts that every
+function and variable defined in the current compilation
+unit is static, except for function @code{main} (note: at
+link time, the current unit is the union of all objects compiled
+with LTO).  Since some functions and variables need to
+be referenced externally, for example by another DSO or from an
+assembler file, GCC also provides the function and variable
+attribute @code{externally_visible} which can be used to disable
+the effect of @option{-fwhole-program} on a specific symbol.
+
+The whole program mode assumptions are slightly more complex in
+C++, where inline functions in headers are put into @emph{COMDAT}
+sections.  COMDAT function and variables can be defined by
+multiple object files and their bodies are unified at link-time
+and dynamic link-time.  COMDAT functions are changed to local only
+when their address is not taken and thus un-sharing them with a
+library is not harmful.  COMDAT variables always remain externally
+visible, however for readonly variables it is assumed that their
+initializers cannot be overwritten by a different value.
+
+GCC provides the function and variable attribute
+@code{visibility} that can be used to specify the visibility of
+externally visible symbols (or alternatively an
+@option{-fdefault-visibility} command line option).  ELF defines
+the @code{default}, @code{protected}, @code{hidden} and
+@code{internal} visibilities.
+
+The most commonly used is visibility is @code{hidden}.  It
+specifies that the symbol cannot be referenced from outside of
+the current shared library.  Unfortunately, this information
+cannot be used directly by the link-time optimization in the
+compiler since the whole shared library also might contain
+non-LTO objects and those are not visible to the compiler.
+
+GCC solves this problem using linker plugins.  A @emph{linker
+plugin} is an interface to the linker that allows an external
+program to claim the ownership of a given object file.  The linker
+then performs the linking procedure by querying the plugin about
+the symbol table of the claimed objects and once the linking
+decisions are complete, the plugin is allowed to provide the
+final object file before the actual linking is made.  The linker
+plugin obtains the symbol resolution information which specifies
+which symbols provided by the claimed objects are bound from the
+rest of a binary being linked.
+
+Currently, the linker plugin  works only in combination
+with the Gold linker, but a GNU ld implementation is under
+development.
+
+GCC is designed to be independent of the rest of the toolchain
+and aims to support linkers without plugin support.  For this
+reason it does not use the linker plugin by default.  Instead,
+the object files are examined by @command{collect2} before being
+passed to the linker and objects found to have LTO sections are
+passed to @command{lto1} first.  This mode does not work for
+library archives.  The decision on what object files from the
+archive are needed depends on the actual linking and thus GCC
+would have to implement the linker itself.  The resolution
+information is missing too and thus GCC needs to make an educated
+guess based on @option{-fwhole-program}.  Without the linker
+plugin GCC also assumes that symbols are declared @code{hidden}
+and not referred by non-LTO code by default.
+
+@section Internal flags controlling @code{lto1}
+
+The following flags are passed into @command{lto1} and are not
+meant to be used directly from the command line.
+
+@itemize
+@item -fwpa
+@opindex fwpa
+This option runs the serial part of the link-time optimizer
+performing the inter-procedural propagation (WPA mode).  The
+compiler reads in summary information from all inputs and
+performs an analysis based on summary information only.  It
+generates object files for subsequent runs of the link-time
+optimizer where individual object files are optimized using both
+summary information from the WPA mode and the actual function
+bodies.  It then drives the LTRANS phase.
+
+@item -fltrans
+@opindex fltrans
+This option runs the link-time optimizer in the
+local-transformation (LTRANS) mode, which reads in output from a
+previous run of the LTO in WPA mode.  In the LTRANS mode, LTO
+optimizes an object and produces the final assembly.
+
+@item -fltrans-output-list=@var{file}
+@opindex fltrans-output-list
+This option specifies a file to which the names of LTRANS output
+files are written.  This option is only meaningful in conjunction
+with @option{-fwpa}.
+@end itemize