<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<!-- Copyright (C) 1988-2015 Free Software Foundation, Inc.

Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License, Version 1.3 or
any later version published by the Free Software Foundation; with the
Invariant Sections being "Funding Free Software", the Front-Cover
Texts being (a) (see below), and with the Back-Cover Texts being (b)
(see below).  A copy of the license is included in the section entitled
"GNU Free Documentation License".

(a) The FSF's Front-Cover Text is:

A GNU Manual

(b) The FSF's Back-Cover Text is:

You have freedom to copy and modify this GNU Manual, like GNU
     software.  Copies published by the Free Software Foundation raise
     funds for GNU development. -->
<!-- Created by GNU Texinfo 5.2, http://www.gnu.org/software/texinfo/ -->
<head>
<title>GNU Compiler Collection (GCC) Internals: IPA</title>

<meta name="description" content="GNU Compiler Collection (GCC) Internals: IPA">
<meta name="keywords" content="GNU Compiler Collection (GCC) Internals: IPA">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<meta name="Generator" content="makeinfo">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<link href="index.html#Top" rel="start" title="Top">
<link href="Option-Index.html#Option-Index" rel="index" title="Option Index">
<link href="index.html#SEC_Contents" rel="contents" title="Table of Contents">
<link href="LTO.html#LTO" rel="up" title="LTO">
<link href="WHOPR.html#WHOPR" rel="next" title="WHOPR">
<link href="LTO-object-file-layout.html#LTO-object-file-layout" rel="prev" title="LTO object file layout">
<style type="text/css">
<!--
a.summary-letter {text-decoration: none}
blockquote.smallquotation {font-size: smaller}
div.display {margin-left: 3.2em}
div.example {margin-left: 3.2em}
div.indentedblock {margin-left: 3.2em}
div.lisp {margin-left: 3.2em}
div.smalldisplay {margin-left: 3.2em}
div.smallexample {margin-left: 3.2em}
div.smallindentedblock {margin-left: 3.2em; font-size: smaller}
div.smalllisp {margin-left: 3.2em}
kbd {font-style:oblique}
pre.display {font-family: inherit}
pre.format {font-family: inherit}
pre.menu-comment {font-family: serif}
pre.menu-preformatted {font-family: serif}
pre.smalldisplay {font-family: inherit; font-size: smaller}
pre.smallexample {font-size: smaller}
pre.smallformat {font-family: inherit; font-size: smaller}
pre.smalllisp {font-size: smaller}
span.nocodebreak {white-space:nowrap}
span.nolinebreak {white-space:nowrap}
span.roman {font-family:serif; font-weight:normal}
span.sansserif {font-family:sans-serif; font-weight:normal}
ul.no-bullet {list-style: none}
-->
</style>


</head>

<body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000">
<a name="IPA"></a>
<div class="header">
<p>
Next: <a href="WHOPR.html#WHOPR" accesskey="n" rel="next">WHOPR</a>, Previous: <a href="LTO-object-file-layout.html#LTO-object-file-layout" accesskey="p" rel="prev">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>
</div>
<hr>
<a name="Using-summary-information-in-IPA-passes"></a>
<h3 class="section">24.3 Using summary information in IPA passes</h3>

<p>Programs are represented internally as a <em>callgraph</em> (a
multi-graph where nodes are functions and edges are call sites)
and a <em>varpool</em> (a list of static and external variables in
the program).
</p>
<p>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:
</p>
<ul>
<li> LGEN time
<ol>
<li> <em>Generate summary</em> (<code>generate_summary</code> in
<code>struct ipa_opt_pass_d</code>).  This stage analyzes every function
body and variable initializer is examined and stores relevant
information into a pass-specific data structure.

</li><li> <em>Write summary</em> (<code>write_summary</code> in
<code>struct ipa_opt_pass_d</code>).  This stage writes all the
pass-specific information generated by <code>generate_summary</code>.
Summaries go into their own <code>LTO_section_*</code> sections that
have to be declared in <samp>lto-streamer.h</samp>:<code>enum
lto_section_type</code>.  A new section is created by calling
<code>create_output_block</code> and data can be written using the
<code>lto_output_*</code> routines.
</li></ol>

</li><li> WPA time
<ol>
<li> <em>Read summary</em> (<code>read_summary</code> in
<code>struct ipa_opt_pass_d</code>).  This stage reads all the
pass-specific information in exactly the same order that it was
written by <code>write_summary</code>.

</li><li> <em>Execute</em> (<code>execute</code> in <code>struct
opt_pass</code>).  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.

</li><li> <em>Write optimization summary</em>
(<code>write_optimization_summary</code> in <code>struct
ipa_opt_pass_d</code>).  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</code>.
</li></ol>

</li><li> LTRANS time
<ol>
<li> <em>Read optimization summary</em>
(<code>read_optimization_summary</code> in <code>struct
ipa_opt_pass_d</code>).  The counterpart to
<code>write_optimization_summary</code>.  This reads the interprocedural
optimization decisions in exactly the same format emitted by
<code>write_optimization_summary</code>.

</li><li> <em>Transform</em> (<code>function_transform</code> and
<code>variable_transform</code> in <code>struct ipa_opt_pass_d</code>).
The actual function bodies and variable initializers are updated
based on the information passed down from the <em>Execute</em> stage.
</li></ol>
</li></ul>

<p>The implementation of the inter-procedural passes are shared
between LTO, WHOPR and classic non-LTO compilation.
</p>
<ul>
<li> During the traditional file-by-file mode every pass executes its
own <em>Generate summary</em>, <em>Execute</em>, and <em>Transform</em>
stages within the single execution context of the compiler.

</li><li> In LTO compilation mode, every pass uses <em>Generate
summary</em> and <em>Write summary</em> stages at compilation time,
while the <em>Read summary</em>, <em>Execute</em>, and
<em>Transform</em> stages are executed at link time.

</li><li> In WHOPR mode all stages are used.
</li></ul>

<p>To simplify development, the GCC pass manager differentiates
between normal inter-procedural passes and small inter-procedural
passes.  A <em>small inter-procedural pass</em>
(<code>SIMPLE_IPA_PASS</code>) is a pass that does
everything at once and thus it can not be executed during WPA in
WHOPR mode.  It defines only the <em>Execute</em> 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.
</p>

<a name="Virtual-clones"></a>
<h4 class="subsection">24.3.1 Virtual clones</h4>

<p>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 <em>Generate summary</em>),
propagation (or <em>Execute</em>) and <em>Transform</em> 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.
</p>
<p>In WHOPR mode all passes first execute their <em>Generate
summary</em> 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
<em>Execute</em> stage.  Optimization summaries are streamed and
sent to LTRANS, where all the passes execute the <em>Transform</em>
stage.
</p>
<p>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 <em>Transform</em> stage and the <em>Generate summary</em>
or <em>Execute</em> stage.  This means that the passes are required
to communicate their decisions with each other.
</p>
<p>To facilitate this communication, the GCC callgraph
infrastructure implements <em>virtual clones</em>, a method of
representing the changes performed by the optimization passes in
the callgraph without needing to update function bodies.
</p>
<p>A <em>virtual clone</em> 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).
</p>
<p>The description of function modifications includes adjustments to
the function&rsquo;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.
</p>
<p>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.
</p>
<p>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.
</p>
<p>Using <em>virtual clones</em>, the program can be easily updated
during the <em>Execute</em> stage, solving most of pass interactions
problems that would otherwise occur during <em>Transform</em>.
</p>
<p>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 <em>Transform</em> 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 <em>Execute</em> stage.
</p>
<p>Optimization passes then work on virtual clones introduced before
their <em>Execute</em> stage as if they were real functions.  The
only difference is that clones are not visible during the
<em>Generate Summary</em> stage.
</p>
<p>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 <em>Generate
summary</em> stage and allow the pass to keep its information intact
until the <em>Execute</em> stage.  The same hooks can also be
registered during the <em>Execute</em> stage to keep the
optimization summaries updated for the <em>Transform</em> stage.
</p>
<a name="IPA-references"></a>
<h4 class="subsection">24.3.2 IPA references</h4>

<p>GCC represents IPA references in the callgraph.  For a function
or variable <code>A</code>, the <em>IPA reference</em> is a list of all
locations where the address of <code>A</code> is taken and, when
<code>A</code> is a variable, a list of all direct stores and reads
to/from <code>A</code>.  References represent an oriented multi-graph on
the union of nodes of the callgraph and the varpool.  See
<samp>ipa-reference.c</samp>:<code>ipa_reference_write_optimization_summary</code>
and
<samp>ipa-reference.c</samp>:<code>ipa_reference_read_optimization_summary</code>
for details.
</p>
<a name="Jump-functions"></a>
<h4 class="subsection">24.3.3 Jump functions</h4>
<p>Suppose that an optimization pass sees a function <code>A</code> and it
knows the values of (some of) its arguments.  The <em>jump
function</em> describes the value of a parameter of a given function
call in function <code>A</code> based on this knowledge.
</p>
<p>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.
</p>
<hr>
<div class="header">
<p>
Next: <a href="WHOPR.html#WHOPR" accesskey="n" rel="next">WHOPR</a>, Previous: <a href="LTO-object-file-layout.html#LTO-object-file-layout" accesskey="p" rel="prev">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>
</div>


</body>
</html>