<!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: Profile information</title>

<meta name="description" content="GNU Compiler Collection (GCC) Internals: Profile information">
<meta name="keywords" content="GNU Compiler Collection (GCC) Internals: Profile information">
<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="Control-Flow.html#Control-Flow" rel="up" title="Control Flow">
<link href="Maintaining-the-CFG.html#Maintaining-the-CFG" rel="next" title="Maintaining the CFG">
<link href="Edges.html#Edges" rel="prev" title="Edges">
<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="Profile-information"></a>
<div class="header">
<p>
Next: <a href="Maintaining-the-CFG.html#Maintaining-the-CFG" accesskey="n" rel="next">Maintaining the CFG</a>, Previous: <a href="Edges.html#Edges" accesskey="p" rel="prev">Edges</a>, Up: <a href="Control-Flow.html#Control-Flow" accesskey="u" rel="up">Control Flow</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="Profile-information-1"></a>
<h3 class="section">14.3 Profile information</h3>

<a name="index-profile-representation"></a>
<p>In many cases a compiler must make a choice whether to trade speed in
one part of code for speed in another, or to trade code size for code
speed.  In such cases it is useful to know information about how often
some given block will be executed.  That is the purpose for
maintaining profile within the flow graph.
GCC can handle profile information obtained through <em>profile
feedback</em>, but it can also estimate branch probabilities based on
statics and heuristics.
</p>
<a name="index-profile-feedback"></a>
<p>The feedback based profile is produced by compiling the program with
instrumentation, executing it on a train run and reading the numbers
of executions of basic blocks and edges back to the compiler while
re-compiling the program to produce the final executable.  This method
provides very accurate information about where a program spends most
of its time on the train run.  Whether it matches the average run of
course depends on the choice of train data set, but several studies
have shown that the behavior of a program usually changes just
marginally over different data sets.
</p>
<a name="index-Static-profile-estimation"></a>
<a name="index-branch-prediction"></a>
<a name="index-predict_002edef"></a>
<p>When profile feedback is not available, the compiler may be asked to
attempt to predict the behavior of each branch in the program using a
set of heuristics (see <samp>predict.def</samp> for details) and compute
estimated frequencies of each basic block by propagating the
probabilities over the graph.
</p>
<a name="index-frequency_002c-count_002c-BB_005fFREQ_005fBASE"></a>
<p>Each <code>basic_block</code> contains two integer fields to represent
profile information: <code>frequency</code> and <code>count</code>.  The
<code>frequency</code> is an estimation how often is basic block executed
within a function.  It is represented as an integer scaled in the
range from 0 to <code>BB_FREQ_BASE</code>.  The most frequently executed
basic block in function is initially set to <code>BB_FREQ_BASE</code> and
the rest of frequencies are scaled accordingly.  During optimization,
the frequency of the most frequent basic block can both decrease (for
instance by loop unrolling) or grow (for instance by cross-jumping
optimization), so scaling sometimes has to be performed multiple
times.
</p>
<a name="index-gcov_005ftype"></a>
<p>The <code>count</code> contains hard-counted numbers of execution measured
during training runs and is nonzero only when profile feedback is
available.  This value is represented as the host&rsquo;s widest integer
(typically a 64 bit integer) of the special type <code>gcov_type</code>.
</p>
<p>Most optimization passes can use only the frequency information of a
basic block, but a few passes may want to know hard execution counts.
The frequencies should always match the counts after scaling, however
during updating of the profile information numerical error may
accumulate into quite large errors.
</p>
<a name="index-REG_005fBR_005fPROB_005fBASE_002c-EDGE_005fFREQUENCY"></a>
<p>Each edge also contains a branch probability field: an integer in the
range from 0 to <code>REG_BR_PROB_BASE</code>.  It represents probability of
passing control from the end of the <code>src</code> basic block to the
<code>dest</code> basic block, i.e. the probability that control will flow
along this edge.  The <code>EDGE_FREQUENCY</code> macro is available to
compute how frequently a given edge is taken.  There is a <code>count</code>
field for each edge as well, representing same information as for a
basic block.
</p>
<p>The basic block frequencies are not represented in the instruction
stream, but in the RTL representation the edge frequencies are
represented for conditional jumps (via the <code>REG_BR_PROB</code>
macro) since they are used when instructions are output to the
assembly file and the flow graph is no longer maintained.
</p>
<a name="index-reverse-probability"></a>
<p>The probability that control flow arrives via a given edge to its
destination basic block is called <em>reverse probability</em> and is not
directly represented, but it may be easily computed from frequencies
of basic blocks.
</p>
<a name="index-redirect_005fedge_005fand_005fbranch"></a>
<p>Updating profile information is a delicate task that can unfortunately
not be easily integrated with the CFG manipulation API.  Many of the
functions and hooks to modify the CFG, such as
<code>redirect_edge_and_branch</code>, do not have enough information to
easily update the profile, so updating it is in the majority of cases
left up to the caller.  It is difficult to uncover bugs in the profile
updating code, because they manifest themselves only by producing
worse code, and checking profile consistency is not possible because
of numeric error accumulation.  Hence special attention needs to be
given to this issue in each pass that modifies the CFG.
</p>
<a name="index-REG_005fBR_005fPROB_005fBASE_002c-BB_005fFREQ_005fBASE_002c-count"></a>
<p>It is important to point out that <code>REG_BR_PROB_BASE</code> and
<code>BB_FREQ_BASE</code> are both set low enough to be possible to compute
second power of any frequency or probability in the flow graph, it is
not possible to even square the <code>count</code> field, as modern CPUs are
fast enough to execute $2^32$ operations quickly.
</p>

<hr>
<div class="header">
<p>
Next: <a href="Maintaining-the-CFG.html#Maintaining-the-CFG" accesskey="n" rel="next">Maintaining the CFG</a>, Previous: <a href="Edges.html#Edges" accesskey="p" rel="prev">Edges</a>, Up: <a href="Control-Flow.html#Control-Flow" accesskey="u" rel="up">Control Flow</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>