cfg.texi

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

@c -*-texinfo-*-
@c Copyright (C) 2001, 2003, 2004, 2005, 2006, 2007, 2008 Free Software
@c Foundation, Inc.
@c This is part of the GCC manual.
@c For copying conditions, see the file gcc.texi.

@c ---------------------------------------------------------------------
@c Control Flow Graph
@c ---------------------------------------------------------------------

@node Control Flow
@chapter Control Flow Graph
@cindex CFG, Control Flow Graph
@findex basic-block.h

A control flow graph (CFG) is a data structure built on top of the
intermediate code representation (the RTL or @code{tree} instruction
stream) abstracting the control flow behavior of a function that is
being compiled.  The CFG is a directed graph where the vertices
represent basic blocks and edges represent possible transfer of
control flow from one basic block to another.  The data structures
used to represent the control flow graph are defined in
@file{basic-block.h}.

@menu
* Basic Blocks::           The definition and representation of basic blocks.
* Edges::                  Types of edges and their representation.
* Profile information::    Representation of frequencies and probabilities.
* Maintaining the CFG::    Keeping the control flow graph and up to date.
* Liveness information::   Using and maintaining liveness information.
@end menu


@node Basic Blocks
@section Basic Blocks

@cindex basic block
@findex basic_block
A basic block is a straight-line sequence of code with only one entry
point and only one exit.  In GCC, basic blocks are represented using
the @code{basic_block} data type.

@findex next_bb, prev_bb, FOR_EACH_BB
Two pointer members of the @code{basic_block} structure are the
pointers @code{next_bb} and @code{prev_bb}.  These are used to keep
doubly linked chain of basic blocks in the same order as the
underlying instruction stream.  The chain of basic blocks is updated
transparently by the provided API for manipulating the CFG@.  The macro
@code{FOR_EACH_BB} can be used to visit all the basic blocks in
lexicographical order.  Dominator traversals are also possible using
@code{walk_dominator_tree}.  Given two basic blocks A and B, block A
dominates block B if A is @emph{always} executed before B@.

@findex BASIC_BLOCK
The @code{BASIC_BLOCK} array contains all basic blocks in an
unspecified order.  Each @code{basic_block} structure has a field
that holds a unique integer identifier @code{index} that is the
index of the block in the @code{BASIC_BLOCK} array.
The total number of basic blocks in the function is
@code{n_basic_blocks}.  Both the basic block indices and
the total number of basic blocks may vary during the compilation
process, as passes reorder, create, duplicate, and destroy basic
blocks.  The index for any block should never be greater than
@code{last_basic_block}.

@findex ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR
Special basic blocks represent possible entry and exit points of a
function.  These blocks are called @code{ENTRY_BLOCK_PTR} and
@code{EXIT_BLOCK_PTR}.  These blocks do not contain any code, and are
not elements of the @code{BASIC_BLOCK} array.  Therefore they have
been assigned unique, negative index numbers.

Each @code{basic_block} also contains pointers to the first
instruction (the @dfn{head}) and the last instruction (the @dfn{tail})
or @dfn{end} of the instruction stream contained in a basic block.  In
fact, since the @code{basic_block} data type is used to represent
blocks in both major intermediate representations of GCC (@code{tree}
and RTL), there are pointers to the head and end of a basic block for
both representations.

@findex NOTE_INSN_BASIC_BLOCK, CODE_LABEL, notes
For RTL, these pointers are @code{rtx head, end}.  In the RTL function
representation, the head pointer always points either to a
@code{NOTE_INSN_BASIC_BLOCK} or to a @code{CODE_LABEL}, if present.
In the RTL representation of a function, the instruction stream
contains not only the ``real'' instructions, but also @dfn{notes}.
Any function that moves or duplicates the basic blocks needs
to take care of updating of these notes.  Many of these notes expect
that the instruction stream consists of linear regions, making such
updates difficult.   The @code{NOTE_INSN_BASIC_BLOCK} note is the only
kind of note that may appear in the instruction stream contained in a
basic block.  The instruction stream of a basic block always follows a
@code{NOTE_INSN_BASIC_BLOCK},  but zero or more @code{CODE_LABEL}
nodes can precede the block note.   A basic block ends by control flow
instruction or last instruction before following @code{CODE_LABEL} or
@code{NOTE_INSN_BASIC_BLOCK}.  A @code{CODE_LABEL} cannot appear in
the instruction stream of a basic block.

@findex can_fallthru
@cindex table jump
In addition to notes, the jump table vectors are also represented as
``pseudo-instructions'' inside the insn stream.  These vectors never
appear in the basic block and should always be placed just after the
table jump instructions referencing them.  After removing the
table-jump it is often difficult to eliminate the code computing the
address and referencing the vector, so cleaning up these vectors is
postponed until after liveness analysis.   Thus the jump table vectors
may appear in the insn stream unreferenced and without any purpose.
Before any edge is made @dfn{fall-thru}, the existence of such
construct in the way needs to be checked by calling
@code{can_fallthru} function.

@cindex block statement iterators
For the @code{tree} representation, the head and end of the basic block
are being pointed to by the @code{stmt_list} field, but this special
@code{tree} should never be referenced directly.  Instead, at the tree
level abstract containers and iterators are used to access statements
and expressions in basic blocks.  These iterators are called
@dfn{block statement iterators} (BSIs).  Grep for @code{^bsi}
in the various @file{tree-*} files.
The following snippet will pretty-print all the statements of the
program in the GIMPLE representation.

@smallexample
FOR_EACH_BB (bb)
  @{
     block_stmt_iterator si;

     for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
       @{
          tree stmt = bsi_stmt (si);
          print_generic_stmt (stderr, stmt, 0);
       @}
  @}
@end smallexample


@node Edges
@section Edges

@cindex edge in the flow graph
@findex edge
Edges represent possible control flow transfers from the end of some
basic block A to the head of another basic block B@.  We say that A is
a predecessor of B, and B is a successor of A@.  Edges are represented
in GCC with the @code{edge} data type.  Each @code{edge} acts as a
link between two basic blocks: the @code{src} member of an edge
points to the predecessor basic block of the @code{dest} basic block.
The members @code{preds} and @code{succs} of the @code{basic_block} data
type point to type-safe vectors of edges to the predecessors and
successors of the block.

@cindex edge iterators
When walking the edges in an edge vector, @dfn{edge iterators} should
be used.  Edge iterators are constructed using the
@code{edge_iterator} data structure and several methods are available
to operate on them:

@ftable @code
@item ei_start
This function initializes an @code{edge_iterator} that points to the
first edge in a vector of edges.

@item ei_last
This function initializes an @code{edge_iterator} that points to the
last edge in a vector of edges.

@item ei_end_p
This predicate is @code{true} if an @code{edge_iterator} represents
the last edge in an edge vector.

@item ei_one_before_end_p
This predicate is @code{true} if an @code{edge_iterator} represents
the second last edge in an edge vector.

@item ei_next
This function takes a pointer to an @code{edge_iterator} and makes it
point to the next edge in the sequence.

@item ei_prev
This function takes a pointer to an @code{edge_iterator} and makes it
point to the previous edge in the sequence.

@item ei_edge
This function returns the @code{edge} currently pointed to by an
@code{edge_iterator}.

@item ei_safe_safe
This function returns the @code{edge} currently pointed to by an
@code{edge_iterator}, but returns @code{NULL} if the iterator is
pointing at the end of the sequence.  This function has been provided
for existing code makes the assumption that a @code{NULL} edge
indicates the end of the sequence.

@end ftable

The convenience macro @code{FOR_EACH_EDGE} can be used to visit all of
the edges in a sequence of predecessor or successor edges.  It must
not be used when an element might be removed during the traversal,
otherwise elements will be missed.  Here is an example of how to use
the macro:

@smallexample
edge e;
edge_iterator ei;

FOR_EACH_EDGE (e, ei, bb->succs)
  @{
     if (e->flags & EDGE_FALLTHRU)
       break;
  @}
@end smallexample

@findex fall-thru
There are various reasons why control flow may transfer from one block
to another.  One possibility is that some instruction, for example a
@code{CODE_LABEL}, in a linearized instruction stream just always
starts a new basic block.  In this case a @dfn{fall-thru} edge links
the basic block to the first following basic block.  But there are
several other reasons why edges may be created.  The @code{flags}
field of the @code{edge} data type is used to store information
about the type of edge we are dealing with.  Each edge is of one of
the following types:

@table @emph
@item jump
No type flags are set for edges corresponding to jump instructions.
These edges are used for unconditional or conditional jumps and in
RTL also for table jumps.  They are the easiest to manipulate as they
may be freely redirected when the flow graph is not in SSA form.

@item fall-thru
@findex EDGE_FALLTHRU, force_nonfallthru
Fall-thru edges are present in case where the basic block may continue
execution to the following one without branching.  These edges have
the @code{EDGE_FALLTHRU} flag set.  Unlike other types of edges, these
edges must come into the basic block immediately following in the
instruction stream.  The function @code{force_nonfallthru} is
available to insert an unconditional jump in the case that redirection
is needed.  Note that this may require creation of a new basic block.

@item exception handling
@cindex exception handling
@findex EDGE_ABNORMAL, EDGE_EH
Exception handling edges represent possible control transfers from a
trapping instruction to an exception handler.  The definition of
``trapping'' varies.  In C++, only function calls can throw, but for
Java, exceptions like division by zero or segmentation fault are
defined and thus each instruction possibly throwing this kind of
exception needs to be handled as control flow instruction.  Exception
edges have the @code{EDGE_ABNORMAL} and @code{EDGE_EH} flags set.

@findex purge_dead_edges
When updating the instruction stream it is easy to change possibly
trapping instruction to non-trapping, by simply removing the exception
edge.  The opposite conversion is difficult, but should not happen
anyway.  The edges can be eliminated via @code{purge_dead_edges} call.

@findex REG_EH_REGION, EDGE_ABNORMAL_CALL
In the RTL representation, the destination of an exception edge is
specified by @code{REG_EH_REGION} note attached to the insn.
In case of a trapping call the @code{EDGE_ABNORMAL_CALL} flag is set
too.  In the @code{tree} representation, this extra flag is not set.

@findex may_trap_p, tree_could_trap_p
In the RTL representation, the predicate @code{may_trap_p} may be used
to check whether instruction still may trap or not.  For the tree
representation, the @code{tree_could_trap_p} predicate is available,
but this predicate only checks for possible memory traps, as in
dereferencing an invalid pointer location.


@item sibling calls
@cindex sibling call
@findex EDGE_ABNORMAL, EDGE_SIBCALL
Sibling calls or tail calls terminate the function in a non-standard
way and thus an edge to the exit must be present.
@code{EDGE_SIBCALL} and @code{EDGE_ABNORMAL} are set in such case.
These edges only exist in the RTL representation.

@item computed jumps
@cindex computed jump
@findex EDGE_ABNORMAL
Computed jumps contain edges to all labels in the function referenced
from the code.  All those edges have @code{EDGE_ABNORMAL} flag set.
The edges used to represent computed jumps often cause compile time
performance problems, since functions consisting of many taken labels
and many computed jumps may have @emph{very} dense flow graphs, so
these edges need to be handled with special care.  During the earlier
stages of the compilation process, GCC tries to avoid such dense flow
graphs by factoring computed jumps.  For example, given the following
series of jumps,

@smallexample
  goto *x;
  [ @dots{} ]

  goto *x;
  [ @dots{} ]

  goto *x;
  [ @dots{} ]
@end smallexample

@noindent
factoring the computed jumps results in the following code sequence
which has a much simpler flow graph:

@smallexample
  goto y;
  [ @dots{} ]

  goto y;
  [ @dots{} ]

  goto y;
  [ @dots{} ]

y:
  goto *x;
@end smallexample

However, the classic problem with this transformation is that it has a
runtime cost in there resulting code: An extra jump.  Therefore, the
computed jumps are un-factored in the later passes of the compiler.
Be aware of that when you work on passes in that area.  There have
been numerous examples already where the compile time for code with
unfactored computed jumps caused some serious headaches.

@item nonlocal goto handlers
@cindex nonlocal goto handler