cfg.texi

理解和实践操作系统的一本好书

@findex EDGE_ABNORMAL, EDGE_ABNORMAL_CALL
GCC allows nested functions to return into caller using a @code{goto}
to a label passed to as an argument to the callee.  The labels passed
to nested functions contain special code to cleanup after function
call.  Such sections of code are referred to as ``nonlocal goto
receivers''.  If a function contains such nonlocal goto receivers, an
edge from the call to the label is created with the
@code{EDGE_ABNORMAL} and @code{EDGE_ABNORMAL_CALL} flags set.

@item function entry points
@cindex function entry point, alternate function entry point
@findex LABEL_ALTERNATE_NAME
By definition, execution of function starts at basic block 0, so there
is always an edge from the @code{ENTRY_BLOCK_PTR} to basic block 0.
There is no @code{tree} representation for alternate entry points at
this moment.  In RTL, alternate entry points are specified by
@code{CODE_LABEL} with @code{LABEL_ALTERNATE_NAME} defined.  This
feature is currently used for multiple entry point prologues and is
limited to post-reload passes only.  This can be used by back-ends to
emit alternate prologues for functions called from different contexts.
In future full support for multiple entry functions defined by Fortran
90 needs to be implemented.

@item function exits
In the pre-reload representation a function terminates after the last
instruction in the insn chain and no explicit return instructions are
used.  This corresponds to the fall-thru edge into exit block.  After
reload, optimal RTL epilogues are used that use explicit (conditional)
return instructions that are represented by edges with no flags set.

@end table


@node Profile information
@section Profile information

@cindex profile representation
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 @dfn{profile
feedback}, but it can also  estimate branch probabilities based on
statics and heuristics.

@cindex profile feedback
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.

@cindex Static profile estimation
@cindex branch prediction
@findex predict.def
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 @file{predict.def} for details) and compute
estimated frequencies of each basic block by propagating the
probabilities over the graph.

@findex frequency, count, BB_FREQ_BASE
Each @code{basic_block} contains two integer fields to represent
profile information: @code{frequency} and @code{count}.  The
@code{frequency} 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}.  The most frequently executed
basic block in function is initially set to @code{BB_FREQ_BASE} 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.

@findex gcov_type
The @code{count} 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's widest integer
(typically a 64 bit integer) of the special type @code{gcov_type}.

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.

@findex REG_BR_PROB_BASE, EDGE_FREQUENCY
Each edge also contains a branch probability field: an integer in the
range from 0 to @code{REG_BR_PROB_BASE}.  It represents probability of
passing control from the end of the @code{src} basic block to the
@code{dest} basic block, i.e.@: the probability that control will flow
along this edge.   The @code{EDGE_FREQUENCY} macro is available to
compute how frequently a given edge is taken.  There is a @code{count}
field for each edge as well, representing same information as for a
basic block.

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}
macro) since they are used when instructions are output to the
assembly file and the flow graph is no longer maintained.

@cindex reverse probability
The probability that control flow arrives via a given edge to its
destination basic block is called @dfn{reverse probability} and is not
directly represented, but it may be easily computed from frequencies
of basic blocks.

@findex redirect_edge_and_branch
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}, 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@.

@findex REG_BR_PROB_BASE, BB_FREQ_BASE, count
It is important to point out that @code{REG_BR_PROB_BASE} and
@code{BB_FREQ_BASE} 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} field, as modern CPUs are
fast enough to execute $2^32$ operations quickly.


@node Maintaining the CFG
@section Maintaining the CFG
@findex cfghooks.h

An important task of each compiler pass is to keep both the control
flow graph and all profile information up-to-date.  Reconstruction of
the control flow graph after each pass is not an option, since it may be
very expensive and lost profile information cannot be reconstructed at
all.

GCC has two major intermediate representations, and both use the
@code{basic_block} and @code{edge} data types to represent control
flow.  Both representations share as much of the CFG maintenance code
as possible.  For each representation, a set of @dfn{hooks} is defined
so that each representation can provide its own implementation of CFG
manipulation routines when necessary.  These hooks are defined in
@file{cfghooks.h}.  There are hooks for almost all common CFG
manipulations, including block splitting and merging, edge redirection
and creating and deleting basic blocks.  These hooks should provide
everything you need to maintain and manipulate the CFG in both the RTL
and @code{tree} representation.

At the moment, the basic block boundaries are maintained transparently
when modifying instructions, so there rarely is a need to move them
manually (such as in case someone wants to output instruction outside
basic block explicitly).
Often the CFG may be better viewed as integral part of instruction
chain, than structure built on the top of it.  However, in principle
the control flow graph for the @code{tree} representation is
@emph{not} an integral part of the representation, in that a function
tree may be expanded without first building a  flow graph for the
@code{tree} representation at all.  This happens when compiling
without any @code{tree} optimization enabled.  When the @code{tree}
optimizations are enabled and the instruction stream is rewritten in
SSA form, the CFG is very tightly coupled with the instruction stream.
In particular, statement insertion and removal has to be done with
care.  In fact, the whole @code{tree} representation can not be easily
used or maintained without proper maintenance of the CFG
simultaneously.

@findex BLOCK_FOR_INSN, bb_for_stmt
In the RTL representation, each instruction has a
@code{BLOCK_FOR_INSN} value that represents pointer to the basic block
that contains the instruction.  In the @code{tree} representation, the
function @code{bb_for_stmt} returns a pointer to the basic block
containing the queried statement.

@cindex block statement iterators
When changes need to be applied to a function in its @code{tree}
representation, @dfn{block statement iterators} should be used.  These
iterators provide an integrated abstraction of the flow graph and the
instruction stream.  Block statement iterators iterators are
constructed using the @code{block_stmt_iterator} data structure and
several modifier are available, including the following:

@ftable @code
@item bsi_start
This function initializes a @code{block_stmt_iterator} that points to
the first non-empty statement in a basic block.

@item bsi_last
This function initializes a @code{block_stmt_iterator} that points to
the last statement in a basic block.

@item bsi_end_p
This predicate is @code{true} if a @code{block_stmt_iterator}
represents the end of a basic block.

@item bsi_next
This function takes a @code{block_stmt_iterator} and makes it point to
its successor.

@item bsi_prev
This function takes a @code{block_stmt_iterator} and makes it point to
its predecessor.

@item bsi_insert_after
This function inserts a statement after the @code{block_stmt_iterator}
passed in.  The final parameter determines whether the statement
iterator is updated to point to the newly inserted statement, or left
pointing to the original statement.

@item bsi_insert_before
This function inserts a statement before the @code{block_stmt_iterator}
passed in.  The final parameter determines whether the statement
iterator is updated to point to the newly inserted statement, or left
pointing to the original  statement.

@item bsi_remove
This function removes the @code{block_stmt_iterator} passed in and
rechains the remaining statements in a basic block, if any.
@end ftable

@findex BB_HEAD, BB_END
In the RTL representation, the macros @code{BB_HEAD} and @code{BB_END}
may be used to get the head and end @code{rtx} of a basic block.  No
abstract iterators are defined for traversing the insn chain, but you
can just use @code{NEXT_INSN} and @code{PREV_INSN} instead.  See
@xref{Insns}.

@findex purge_dead_edges
Usually a code manipulating pass simplifies the instruction stream and
the flow of control, possibly eliminating some edges.  This may for
example happen when a conditional jump is replaced with an
unconditional jump, but also when simplifying possibly trapping
instruction to non-trapping while compiling Java.  Updating of edges
is not transparent and each optimization pass is required to do so
manually.  However only few cases occur in practice.  The pass may
call @code{purge_dead_edges} on a given basic block to remove
superfluous edges, if any.

@findex redirect_edge_and_branch, redirect_jump
Another common scenario is redirection of branch instructions, but
this is best modeled as redirection of edges in the control flow graph
and thus use of @code{redirect_edge_and_branch} is preferred over more
low level functions, such as @code{redirect_jump} that operate on RTL
chain only.  The CFG hooks defined in @file{cfghooks.h} should provide
the complete API required for manipulating and maintaining the CFG@.

@findex split_block
It is also possible that a pass has to insert control flow instruction
into the middle of a basic block, thus creating an entry point in the
middle of the basic block, which is impossible by definition: The
block must be split to make sure it only has one entry point, i.e.@: the
head of the basic block.  The CFG hook @code{split_block} may be used
when an instruction in the middle of a basic block has to become the
target of a jump or branch instruction.

@findex insert_insn_on_edge
@findex commit_edge_insertions
@findex bsi_insert_on_edge
@findex bsi_commit_edge_inserts
@cindex edge splitting
For a global optimizer, a common operation is to split edges in the
flow graph and insert instructions on them.  In the RTL
representation, this can be easily done using the
@code{insert_insn_on_edge} function that emits an instruction
``on the edge'', caching it for a later @code{commit_edge_insertions}
call that will take care of moving the inserted instructions off the
edge into the instruction stream contained in a basic block.  This
includes the creation of new basic blocks where needed.  In the
@code{tree} representation, the equivalent functions are
@code{bsi_insert_on_edge} which inserts a block statement
iterator on an edge, and @code{bsi_commit_edge_inserts} which flushes
the instruction to actual instruction stream.

While debugging the optimization pass, an @code{verify_flow_info}
function may be useful to find bugs in the control flow graph updating
code.

Note that at present, the representation of control flow in the
@code{tree} representation is discarded before expanding to RTL@.
Long term the CFG should be maintained and ``expanded'' to the
RTL representation along with the function @code{tree} itself.


@node Liveness information
@section Liveness information
@cindex Liveness representation
Liveness information is useful to determine whether some register is
``live'' at given point of program, i.e.@: that it contains a value that
may be used at a later point in the program.  This information is
used, for instance, during register allocation, as the pseudo
registers only need to be assigned to a unique hard register or to a
stack slot if they are live.  The hard registers and stack slots may
be freely reused for other values when a register is dead.  

Liveness information is available in the back end starting with
@code{pass_df_initialize} and ending with @code{pass_df_finish}.  Three
flavors of live analysis are available: With @code{LR}, it is possible
to determine at any point @code{P} in the function if the register may be
used on some path from @code{P} to the end of the function.  With
@code{UR}, it is possible to determine if there is a path from the
beginning of the function to @code{P} that defines the variable.  
@code{LIVE} is the intersection of the @code{LR} and @code{UR} and a
variable is live at @code{P} if there is both an assignment that reaches
it from the beginning of the function and a uses that can be reached on
some path from @code{P} to the end of the function.

In general @code{LIVE} is the most useful of the three.  The macros
@code{DF_[LR,UR,LIVE]_[IN,OUT]} can be used to access this information.
The macros take a basic block number and return a bitmap that is indexed
by the register number.  This information is only guaranteed to be up to
date after calls are made to @code{df_analyze}.  See the file
@code{df-core.c} for details on using the dataflow.  


@findex REG_DEAD, REG_UNUSED
The liveness information is stored partly in the RTL instruction stream
and partly in the flow graph.  Local information is stored in the
instruction stream: Each instruction may contain @code{REG_DEAD} notes
representing that the value of a given register is no longer needed, or
@code{REG_UNUSED} notes representing that the value computed by the
instruction is never used.  The second is useful for instructions
computing multiple values at once.