@c -*-texinfo-*-
|
@c -*-texinfo-*-
|
@c Copyright (C) 2001, 2003, 2004, 2005, 2006, 2007, 2008 Free Software
|
@c Copyright (C) 2001, 2003, 2004, 2005, 2006, 2007, 2008 Free Software
|
@c Foundation, Inc.
|
@c Foundation, Inc.
|
@c This is part of the GCC manual.
|
@c This is part of the GCC manual.
|
@c For copying conditions, see the file gcc.texi.
|
@c For copying conditions, see the file gcc.texi.
|
|
|
@c ---------------------------------------------------------------------
|
@c ---------------------------------------------------------------------
|
@c Control Flow Graph
|
@c Control Flow Graph
|
@c ---------------------------------------------------------------------
|
@c ---------------------------------------------------------------------
|
|
|
@node Control Flow
|
@node Control Flow
|
@chapter Control Flow Graph
|
@chapter Control Flow Graph
|
@cindex CFG, Control Flow Graph
|
@cindex CFG, Control Flow Graph
|
@findex basic-block.h
|
@findex basic-block.h
|
|
|
A control flow graph (CFG) is a data structure built on top of the
|
A control flow graph (CFG) is a data structure built on top of the
|
intermediate code representation (the RTL or @code{tree} instruction
|
intermediate code representation (the RTL or @code{tree} instruction
|
stream) abstracting the control flow behavior of a function that is
|
stream) abstracting the control flow behavior of a function that is
|
being compiled. The CFG is a directed graph where the vertices
|
being compiled. The CFG is a directed graph where the vertices
|
represent basic blocks and edges represent possible transfer of
|
represent basic blocks and edges represent possible transfer of
|
control flow from one basic block to another. The data structures
|
control flow from one basic block to another. The data structures
|
used to represent the control flow graph are defined in
|
used to represent the control flow graph are defined in
|
@file{basic-block.h}.
|
@file{basic-block.h}.
|
|
|
@menu
|
@menu
|
* Basic Blocks:: The definition and representation of basic blocks.
|
* Basic Blocks:: The definition and representation of basic blocks.
|
* Edges:: Types of edges and their representation.
|
* Edges:: Types of edges and their representation.
|
* Profile information:: Representation of frequencies and probabilities.
|
* Profile information:: Representation of frequencies and probabilities.
|
* Maintaining the CFG:: Keeping the control flow graph and up to date.
|
* Maintaining the CFG:: Keeping the control flow graph and up to date.
|
* Liveness information:: Using and maintaining liveness information.
|
* Liveness information:: Using and maintaining liveness information.
|
@end menu
|
@end menu
|
|
|
|
|
@node Basic Blocks
|
@node Basic Blocks
|
@section Basic Blocks
|
@section Basic Blocks
|
|
|
@cindex basic block
|
@cindex basic block
|
@findex basic_block
|
@findex basic_block
|
A basic block is a straight-line sequence of code with only one entry
|
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
|
point and only one exit. In GCC, basic blocks are represented using
|
the @code{basic_block} data type.
|
the @code{basic_block} data type.
|
|
|
@findex next_bb, prev_bb, FOR_EACH_BB
|
@findex next_bb, prev_bb, FOR_EACH_BB
|
Two pointer members of the @code{basic_block} structure are the
|
Two pointer members of the @code{basic_block} structure are the
|
pointers @code{next_bb} and @code{prev_bb}. These are used to keep
|
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
|
doubly linked chain of basic blocks in the same order as the
|
underlying instruction stream. The chain of basic blocks is updated
|
underlying instruction stream. The chain of basic blocks is updated
|
transparently by the provided API for manipulating the CFG@. The macro
|
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
|
@code{FOR_EACH_BB} can be used to visit all the basic blocks in
|
lexicographical order. Dominator traversals are also possible using
|
lexicographical order. Dominator traversals are also possible using
|
@code{walk_dominator_tree}. Given two basic blocks A and B, block A
|
@code{walk_dominator_tree}. Given two basic blocks A and B, block A
|
dominates block B if A is @emph{always} executed before B@.
|
dominates block B if A is @emph{always} executed before B@.
|
|
|
@findex BASIC_BLOCK
|
@findex BASIC_BLOCK
|
The @code{BASIC_BLOCK} array contains all basic blocks in an
|
The @code{BASIC_BLOCK} array contains all basic blocks in an
|
unspecified order. Each @code{basic_block} structure has a field
|
unspecified order. Each @code{basic_block} structure has a field
|
that holds a unique integer identifier @code{index} that is the
|
that holds a unique integer identifier @code{index} that is the
|
index of the block in the @code{BASIC_BLOCK} array.
|
index of the block in the @code{BASIC_BLOCK} array.
|
The total number of basic blocks in the function is
|
The total number of basic blocks in the function is
|
@code{n_basic_blocks}. Both the basic block indices and
|
@code{n_basic_blocks}. Both the basic block indices and
|
the total number of basic blocks may vary during the compilation
|
the total number of basic blocks may vary during the compilation
|
process, as passes reorder, create, duplicate, and destroy basic
|
process, as passes reorder, create, duplicate, and destroy basic
|
blocks. The index for any block should never be greater than
|
blocks. The index for any block should never be greater than
|
@code{last_basic_block}.
|
@code{last_basic_block}.
|
|
|
@findex ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR
|
@findex ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR
|
Special basic blocks represent possible entry and exit points of a
|
Special basic blocks represent possible entry and exit points of a
|
function. These blocks are called @code{ENTRY_BLOCK_PTR} and
|
function. These blocks are called @code{ENTRY_BLOCK_PTR} and
|
@code{EXIT_BLOCK_PTR}. These blocks do not contain any code, and are
|
@code{EXIT_BLOCK_PTR}. These blocks do not contain any code, and are
|
not elements of the @code{BASIC_BLOCK} array. Therefore they have
|
not elements of the @code{BASIC_BLOCK} array. Therefore they have
|
been assigned unique, negative index numbers.
|
been assigned unique, negative index numbers.
|
|
|
Each @code{basic_block} also contains pointers to the first
|
Each @code{basic_block} also contains pointers to the first
|
instruction (the @dfn{head}) and the last instruction (the @dfn{tail})
|
instruction (the @dfn{head}) and the last instruction (the @dfn{tail})
|
or @dfn{end} of the instruction stream contained in a basic block. In
|
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
|
fact, since the @code{basic_block} data type is used to represent
|
blocks in both major intermediate representations of GCC (@code{tree}
|
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
|
and RTL), there are pointers to the head and end of a basic block for
|
both representations.
|
both representations.
|
|
|
@findex NOTE_INSN_BASIC_BLOCK, CODE_LABEL, notes
|
@findex NOTE_INSN_BASIC_BLOCK, CODE_LABEL, notes
|
For RTL, these pointers are @code{rtx head, end}. In the RTL function
|
For RTL, these pointers are @code{rtx head, end}. In the RTL function
|
representation, the head pointer always points either to a
|
representation, the head pointer always points either to a
|
@code{NOTE_INSN_BASIC_BLOCK} or to a @code{CODE_LABEL}, if present.
|
@code{NOTE_INSN_BASIC_BLOCK} or to a @code{CODE_LABEL}, if present.
|
In the RTL representation of a function, the instruction stream
|
In the RTL representation of a function, the instruction stream
|
contains not only the ``real'' instructions, but also @dfn{notes}.
|
contains not only the ``real'' instructions, but also @dfn{notes}.
|
Any function that moves or duplicates the basic blocks needs
|
Any function that moves or duplicates the basic blocks needs
|
to take care of updating of these notes. Many of these notes expect
|
to take care of updating of these notes. Many of these notes expect
|
that the instruction stream consists of linear regions, making such
|
that the instruction stream consists of linear regions, making such
|
updates difficult. The @code{NOTE_INSN_BASIC_BLOCK} note is the only
|
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
|
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
|
basic block. The instruction stream of a basic block always follows a
|
@code{NOTE_INSN_BASIC_BLOCK}, but zero or more @code{CODE_LABEL}
|
@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
|
nodes can precede the block note. A basic block ends by control flow
|
instruction or last instruction before following @code{CODE_LABEL} or
|
instruction or last instruction before following @code{CODE_LABEL} or
|
@code{NOTE_INSN_BASIC_BLOCK}. A @code{CODE_LABEL} cannot appear in
|
@code{NOTE_INSN_BASIC_BLOCK}. A @code{CODE_LABEL} cannot appear in
|
the instruction stream of a basic block.
|
the instruction stream of a basic block.
|
|
|
@findex can_fallthru
|
@findex can_fallthru
|
@cindex table jump
|
@cindex table jump
|
In addition to notes, the jump table vectors are also represented as
|
In addition to notes, the jump table vectors are also represented as
|
``pseudo-instructions'' inside the insn stream. These vectors never
|
``pseudo-instructions'' inside the insn stream. These vectors never
|
appear in the basic block and should always be placed just after the
|
appear in the basic block and should always be placed just after the
|
table jump instructions referencing them. After removing the
|
table jump instructions referencing them. After removing the
|
table-jump it is often difficult to eliminate the code computing the
|
table-jump it is often difficult to eliminate the code computing the
|
address and referencing the vector, so cleaning up these vectors is
|
address and referencing the vector, so cleaning up these vectors is
|
postponed until after liveness analysis. Thus the jump table vectors
|
postponed until after liveness analysis. Thus the jump table vectors
|
may appear in the insn stream unreferenced and without any purpose.
|
may appear in the insn stream unreferenced and without any purpose.
|
Before any edge is made @dfn{fall-thru}, the existence of such
|
Before any edge is made @dfn{fall-thru}, the existence of such
|
construct in the way needs to be checked by calling
|
construct in the way needs to be checked by calling
|
@code{can_fallthru} function.
|
@code{can_fallthru} function.
|
|
|
@cindex block statement iterators
|
@cindex block statement iterators
|
For the @code{tree} representation, the head and end of the basic block
|
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
|
are being pointed to by the @code{stmt_list} field, but this special
|
@code{tree} should never be referenced directly. Instead, at the tree
|
@code{tree} should never be referenced directly. Instead, at the tree
|
level abstract containers and iterators are used to access statements
|
level abstract containers and iterators are used to access statements
|
and expressions in basic blocks. These iterators are called
|
and expressions in basic blocks. These iterators are called
|
@dfn{block statement iterators} (BSIs). Grep for @code{^bsi}
|
@dfn{block statement iterators} (BSIs). Grep for @code{^bsi}
|
in the various @file{tree-*} files.
|
in the various @file{tree-*} files.
|
The following snippet will pretty-print all the statements of the
|
The following snippet will pretty-print all the statements of the
|
program in the GIMPLE representation.
|
program in the GIMPLE representation.
|
|
|
@smallexample
|
@smallexample
|
FOR_EACH_BB (bb)
|
FOR_EACH_BB (bb)
|
@{
|
@{
|
block_stmt_iterator si;
|
block_stmt_iterator si;
|
|
|
for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
|
for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
|
@{
|
@{
|
tree stmt = bsi_stmt (si);
|
tree stmt = bsi_stmt (si);
|
print_generic_stmt (stderr, stmt, 0);
|
print_generic_stmt (stderr, stmt, 0);
|
@}
|
@}
|
@}
|
@}
|
@end smallexample
|
@end smallexample
|
|
|
|
|
@node Edges
|
@node Edges
|
@section Edges
|
@section Edges
|
|
|
@cindex edge in the flow graph
|
@cindex edge in the flow graph
|
@findex edge
|
@findex edge
|
Edges represent possible control flow transfers from the end of some
|
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
|
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
|
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
|
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
|
link between two basic blocks: the @code{src} member of an edge
|
points to the predecessor basic block of the @code{dest} basic block.
|
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
|
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
|
type point to type-safe vectors of edges to the predecessors and
|
successors of the block.
|
successors of the block.
|
|
|
@cindex edge iterators
|
@cindex edge iterators
|
When walking the edges in an edge vector, @dfn{edge iterators} should
|
When walking the edges in an edge vector, @dfn{edge iterators} should
|
be used. Edge iterators are constructed using the
|
be used. Edge iterators are constructed using the
|
@code{edge_iterator} data structure and several methods are available
|
@code{edge_iterator} data structure and several methods are available
|
to operate on them:
|
to operate on them:
|
|
|
@ftable @code
|
@ftable @code
|
@item ei_start
|
@item ei_start
|
This function initializes an @code{edge_iterator} that points to the
|
This function initializes an @code{edge_iterator} that points to the
|
first edge in a vector of edges.
|
first edge in a vector of edges.
|
|
|
@item ei_last
|
@item ei_last
|
This function initializes an @code{edge_iterator} that points to the
|
This function initializes an @code{edge_iterator} that points to the
|
last edge in a vector of edges.
|
last edge in a vector of edges.
|
|
|
@item ei_end_p
|
@item ei_end_p
|
This predicate is @code{true} if an @code{edge_iterator} represents
|
This predicate is @code{true} if an @code{edge_iterator} represents
|
the last edge in an edge vector.
|
the last edge in an edge vector.
|
|
|
@item ei_one_before_end_p
|
@item ei_one_before_end_p
|
This predicate is @code{true} if an @code{edge_iterator} represents
|
This predicate is @code{true} if an @code{edge_iterator} represents
|
the second last edge in an edge vector.
|
the second last edge in an edge vector.
|
|
|
@item ei_next
|
@item ei_next
|
This function takes a pointer to an @code{edge_iterator} and makes it
|
This function takes a pointer to an @code{edge_iterator} and makes it
|
point to the next edge in the sequence.
|
point to the next edge in the sequence.
|
|
|
@item ei_prev
|
@item ei_prev
|
This function takes a pointer to an @code{edge_iterator} and makes it
|
This function takes a pointer to an @code{edge_iterator} and makes it
|
point to the previous edge in the sequence.
|
point to the previous edge in the sequence.
|
|
|
@item ei_edge
|
@item ei_edge
|
This function returns the @code{edge} currently pointed to by an
|
This function returns the @code{edge} currently pointed to by an
|
@code{edge_iterator}.
|
@code{edge_iterator}.
|
|
|
@item ei_safe_safe
|
@item ei_safe_safe
|
This function returns the @code{edge} currently pointed to by an
|
This function returns the @code{edge} currently pointed to by an
|
@code{edge_iterator}, but returns @code{NULL} if the iterator is
|
@code{edge_iterator}, but returns @code{NULL} if the iterator is
|
pointing at the end of the sequence. This function has been provided
|
pointing at the end of the sequence. This function has been provided
|
for existing code makes the assumption that a @code{NULL} edge
|
for existing code makes the assumption that a @code{NULL} edge
|
indicates the end of the sequence.
|
indicates the end of the sequence.
|
|
|
@end ftable
|
@end ftable
|
|
|
The convenience macro @code{FOR_EACH_EDGE} can be used to visit all of
|
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
|
the edges in a sequence of predecessor or successor edges. It must
|
not be used when an element might be removed during the traversal,
|
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
|
otherwise elements will be missed. Here is an example of how to use
|
the macro:
|
the macro:
|
|
|
@smallexample
|
@smallexample
|
edge e;
|
edge e;
|
edge_iterator ei;
|
edge_iterator ei;
|
|
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
FOR_EACH_EDGE (e, ei, bb->succs)
|
@{
|
@{
|
if (e->flags & EDGE_FALLTHRU)
|
if (e->flags & EDGE_FALLTHRU)
|
break;
|
break;
|
@}
|
@}
|
@end smallexample
|
@end smallexample
|
|
|
@findex fall-thru
|
@findex fall-thru
|
There are various reasons why control flow may transfer from one block
|
There are various reasons why control flow may transfer from one block
|
to another. One possibility is that some instruction, for example a
|
to another. One possibility is that some instruction, for example a
|
@code{CODE_LABEL}, in a linearized instruction stream just always
|
@code{CODE_LABEL}, in a linearized instruction stream just always
|
starts a new basic block. In this case a @dfn{fall-thru} edge links
|
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
|
the basic block to the first following basic block. But there are
|
several other reasons why edges may be created. The @code{flags}
|
several other reasons why edges may be created. The @code{flags}
|
field of the @code{edge} data type is used to store information
|
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
|
about the type of edge we are dealing with. Each edge is of one of
|
the following types:
|
the following types:
|
|
|
@table @emph
|
@table @emph
|
@item jump
|
@item jump
|
No type flags are set for edges corresponding to jump instructions.
|
No type flags are set for edges corresponding to jump instructions.
|
These edges are used for unconditional or conditional jumps and in
|
These edges are used for unconditional or conditional jumps and in
|
RTL also for table jumps. They are the easiest to manipulate as they
|
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.
|
may be freely redirected when the flow graph is not in SSA form.
|
|
|
@item fall-thru
|
@item fall-thru
|
@findex EDGE_FALLTHRU, force_nonfallthru
|
@findex EDGE_FALLTHRU, force_nonfallthru
|
Fall-thru edges are present in case where the basic block may continue
|
Fall-thru edges are present in case where the basic block may continue
|
execution to the following one without branching. These edges have
|
execution to the following one without branching. These edges have
|
the @code{EDGE_FALLTHRU} flag set. Unlike other types of edges, these
|
the @code{EDGE_FALLTHRU} flag set. Unlike other types of edges, these
|
edges must come into the basic block immediately following in the
|
edges must come into the basic block immediately following in the
|
instruction stream. The function @code{force_nonfallthru} is
|
instruction stream. The function @code{force_nonfallthru} is
|
available to insert an unconditional jump in the case that redirection
|
available to insert an unconditional jump in the case that redirection
|
is needed. Note that this may require creation of a new basic block.
|
is needed. Note that this may require creation of a new basic block.
|
|
|
@item exception handling
|
@item exception handling
|
@cindex exception handling
|
@cindex exception handling
|
@findex EDGE_ABNORMAL, EDGE_EH
|
@findex EDGE_ABNORMAL, EDGE_EH
|
Exception handling edges represent possible control transfers from a
|
Exception handling edges represent possible control transfers from a
|
trapping instruction to an exception handler. The definition of
|
trapping instruction to an exception handler. The definition of
|
``trapping'' varies. In C++, only function calls can throw, but for
|
``trapping'' varies. In C++, only function calls can throw, but for
|
Java, exceptions like division by zero or segmentation fault are
|
Java, exceptions like division by zero or segmentation fault are
|
defined and thus each instruction possibly throwing this kind of
|
defined and thus each instruction possibly throwing this kind of
|
exception needs to be handled as control flow instruction. Exception
|
exception needs to be handled as control flow instruction. Exception
|
edges have the @code{EDGE_ABNORMAL} and @code{EDGE_EH} flags set.
|
edges have the @code{EDGE_ABNORMAL} and @code{EDGE_EH} flags set.
|
|
|
@findex purge_dead_edges
|
@findex purge_dead_edges
|
When updating the instruction stream it is easy to change possibly
|
When updating the instruction stream it is easy to change possibly
|
trapping instruction to non-trapping, by simply removing the exception
|
trapping instruction to non-trapping, by simply removing the exception
|
edge. The opposite conversion is difficult, but should not happen
|
edge. The opposite conversion is difficult, but should not happen
|
anyway. The edges can be eliminated via @code{purge_dead_edges} call.
|
anyway. The edges can be eliminated via @code{purge_dead_edges} call.
|
|
|
@findex REG_EH_REGION, EDGE_ABNORMAL_CALL
|
@findex REG_EH_REGION, EDGE_ABNORMAL_CALL
|
In the RTL representation, the destination of an exception edge is
|
In the RTL representation, the destination of an exception edge is
|
specified by @code{REG_EH_REGION} note attached to the insn.
|
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
|
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.
|
too. In the @code{tree} representation, this extra flag is not set.
|
|
|
@findex may_trap_p, tree_could_trap_p
|
@findex may_trap_p, tree_could_trap_p
|
In the RTL representation, the predicate @code{may_trap_p} may be used
|
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
|
to check whether instruction still may trap or not. For the tree
|
representation, the @code{tree_could_trap_p} predicate is available,
|
representation, the @code{tree_could_trap_p} predicate is available,
|
but this predicate only checks for possible memory traps, as in
|
but this predicate only checks for possible memory traps, as in
|
dereferencing an invalid pointer location.
|
dereferencing an invalid pointer location.
|
|
|
|
|
@item sibling calls
|
@item sibling calls
|
@cindex sibling call
|
@cindex sibling call
|
@findex EDGE_ABNORMAL, EDGE_SIBCALL
|
@findex EDGE_ABNORMAL, EDGE_SIBCALL
|
Sibling calls or tail calls terminate the function in a non-standard
|
Sibling calls or tail calls terminate the function in a non-standard
|
way and thus an edge to the exit must be present.
|
way and thus an edge to the exit must be present.
|
@code{EDGE_SIBCALL} and @code{EDGE_ABNORMAL} are set in such case.
|
@code{EDGE_SIBCALL} and @code{EDGE_ABNORMAL} are set in such case.
|
These edges only exist in the RTL representation.
|
These edges only exist in the RTL representation.
|
|
|
@item computed jumps
|
@item computed jumps
|
@cindex computed jump
|
@cindex computed jump
|
@findex EDGE_ABNORMAL
|
@findex EDGE_ABNORMAL
|
Computed jumps contain edges to all labels in the function referenced
|
Computed jumps contain edges to all labels in the function referenced
|
from the code. All those edges have @code{EDGE_ABNORMAL} flag set.
|
from the code. All those edges have @code{EDGE_ABNORMAL} flag set.
|
The edges used to represent computed jumps often cause compile time
|
The edges used to represent computed jumps often cause compile time
|
performance problems, since functions consisting of many taken labels
|
performance problems, since functions consisting of many taken labels
|
and many computed jumps may have @emph{very} dense flow graphs, so
|
and many computed jumps may have @emph{very} dense flow graphs, so
|
these edges need to be handled with special care. During the earlier
|
these edges need to be handled with special care. During the earlier
|
stages of the compilation process, GCC tries to avoid such dense flow
|
stages of the compilation process, GCC tries to avoid such dense flow
|
graphs by factoring computed jumps. For example, given the following
|
graphs by factoring computed jumps. For example, given the following
|
series of jumps,
|
series of jumps,
|
|
|
@smallexample
|
@smallexample
|
goto *x;
|
goto *x;
|
[ @dots{} ]
|
[ @dots{} ]
|
|
|
goto *x;
|
goto *x;
|
[ @dots{} ]
|
[ @dots{} ]
|
|
|
goto *x;
|
goto *x;
|
[ @dots{} ]
|
[ @dots{} ]
|
@end smallexample
|
@end smallexample
|
|
|
@noindent
|
@noindent
|
factoring the computed jumps results in the following code sequence
|
factoring the computed jumps results in the following code sequence
|
which has a much simpler flow graph:
|
which has a much simpler flow graph:
|
|
|
@smallexample
|
@smallexample
|
goto y;
|
goto y;
|
[ @dots{} ]
|
[ @dots{} ]
|
|
|
goto y;
|
goto y;
|
[ @dots{} ]
|
[ @dots{} ]
|
|
|
goto y;
|
goto y;
|
[ @dots{} ]
|
[ @dots{} ]
|
|
|
y:
|
y:
|
goto *x;
|
goto *x;
|
@end smallexample
|
@end smallexample
|
|
|
However, the classic problem with this transformation is that it has a
|
However, the classic problem with this transformation is that it has a
|
runtime cost in there resulting code: An extra jump. Therefore, the
|
runtime cost in there resulting code: An extra jump. Therefore, the
|
computed jumps are un-factored in the later passes of the compiler.
|
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
|
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
|
been numerous examples already where the compile time for code with
|
unfactored computed jumps caused some serious headaches.
|
unfactored computed jumps caused some serious headaches.
|
|
|
@item nonlocal goto handlers
|
@item nonlocal goto handlers
|
@cindex nonlocal goto handler
|
@cindex nonlocal goto handler
|
@findex EDGE_ABNORMAL, EDGE_ABNORMAL_CALL
|
@findex EDGE_ABNORMAL, EDGE_ABNORMAL_CALL
|
GCC allows nested functions to return into caller using a @code{goto}
|
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 a label passed to as an argument to the callee. The labels passed
|
to nested functions contain special code to cleanup after function
|
to nested functions contain special code to cleanup after function
|
call. Such sections of code are referred to as ``nonlocal goto
|
call. Such sections of code are referred to as ``nonlocal goto
|
receivers''. If a function contains such nonlocal goto receivers, an
|
receivers''. If a function contains such nonlocal goto receivers, an
|
edge from the call to the label is created with the
|
edge from the call to the label is created with the
|
@code{EDGE_ABNORMAL} and @code{EDGE_ABNORMAL_CALL} flags set.
|
@code{EDGE_ABNORMAL} and @code{EDGE_ABNORMAL_CALL} flags set.
|
|
|
@item function entry points
|
@item function entry points
|
@cindex function entry point, alternate function entry point
|
@cindex function entry point, alternate function entry point
|
@findex LABEL_ALTERNATE_NAME
|
@findex LABEL_ALTERNATE_NAME
|
By definition, execution of function starts at basic block 0, so there
|
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.
|
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
|
There is no @code{tree} representation for alternate entry points at
|
this moment. In RTL, alternate entry points are specified by
|
this moment. In RTL, alternate entry points are specified by
|
@code{CODE_LABEL} with @code{LABEL_ALTERNATE_NAME} defined. This
|
@code{CODE_LABEL} with @code{LABEL_ALTERNATE_NAME} defined. This
|
feature is currently used for multiple entry point prologues and is
|
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
|
limited to post-reload passes only. This can be used by back-ends to
|
emit alternate prologues for functions called from different contexts.
|
emit alternate prologues for functions called from different contexts.
|
In future full support for multiple entry functions defined by Fortran
|
In future full support for multiple entry functions defined by Fortran
|
90 needs to be implemented.
|
90 needs to be implemented.
|
|
|
@item function exits
|
@item function exits
|
In the pre-reload representation a function terminates after the last
|
In the pre-reload representation a function terminates after the last
|
instruction in the insn chain and no explicit return instructions are
|
instruction in the insn chain and no explicit return instructions are
|
used. This corresponds to the fall-thru edge into exit block. After
|
used. This corresponds to the fall-thru edge into exit block. After
|
reload, optimal RTL epilogues are used that use explicit (conditional)
|
reload, optimal RTL epilogues are used that use explicit (conditional)
|
return instructions that are represented by edges with no flags set.
|
return instructions that are represented by edges with no flags set.
|
|
|
@end table
|
@end table
|
|
|
|
|
@node Profile information
|
@node Profile information
|
@section Profile information
|
@section Profile information
|
|
|
@cindex profile representation
|
@cindex profile representation
|
In many cases a compiler must make a choice whether to trade speed in
|
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
|
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
|
speed. In such cases it is useful to know information about how often
|
some given block will be executed. That is the purpose for
|
some given block will be executed. That is the purpose for
|
maintaining profile within the flow graph.
|
maintaining profile within the flow graph.
|
GCC can handle profile information obtained through @dfn{profile
|
GCC can handle profile information obtained through @dfn{profile
|
feedback}, but it can also estimate branch probabilities based on
|
feedback}, but it can also estimate branch probabilities based on
|
statics and heuristics.
|
statics and heuristics.
|
|
|
@cindex profile feedback
|
@cindex profile feedback
|
The feedback based profile is produced by compiling the program with
|
The feedback based profile is produced by compiling the program with
|
instrumentation, executing it on a train run and reading the numbers
|
instrumentation, executing it on a train run and reading the numbers
|
of executions of basic blocks and edges back to the compiler while
|
of executions of basic blocks and edges back to the compiler while
|
re-compiling the program to produce the final executable. This method
|
re-compiling the program to produce the final executable. This method
|
provides very accurate information about where a program spends most
|
provides very accurate information about where a program spends most
|
of its time on the train run. Whether it matches the average run of
|
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
|
course depends on the choice of train data set, but several studies
|
have shown that the behavior of a program usually changes just
|
have shown that the behavior of a program usually changes just
|
marginally over different data sets.
|
marginally over different data sets.
|
|
|
@cindex Static profile estimation
|
@cindex Static profile estimation
|
@cindex branch prediction
|
@cindex branch prediction
|
@findex predict.def
|
@findex predict.def
|
When profile feedback is not available, the compiler may be asked to
|
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
|
attempt to predict the behavior of each branch in the program using a
|
set of heuristics (see @file{predict.def} for details) and compute
|
set of heuristics (see @file{predict.def} for details) and compute
|
estimated frequencies of each basic block by propagating the
|
estimated frequencies of each basic block by propagating the
|
probabilities over the graph.
|
probabilities over the graph.
|
|
|
@findex frequency, count, BB_FREQ_BASE
|
@findex frequency, count, BB_FREQ_BASE
|
Each @code{basic_block} contains two integer fields to represent
|
Each @code{basic_block} contains two integer fields to represent
|
profile information: @code{frequency} and @code{count}. The
|
profile information: @code{frequency} and @code{count}. The
|
@code{frequency} is an estimation how often is basic block executed
|
@code{frequency} is an estimation how often is basic block executed
|
within a function. It is represented as an integer scaled in the
|
within a function. It is represented as an integer scaled in the
|
range from 0 to @code{BB_FREQ_BASE}. The most frequently executed
|
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
|
basic block in function is initially set to @code{BB_FREQ_BASE} and
|
the rest of frequencies are scaled accordingly. During optimization,
|
the rest of frequencies are scaled accordingly. During optimization,
|
the frequency of the most frequent basic block can both decrease (for
|
the frequency of the most frequent basic block can both decrease (for
|
instance by loop unrolling) or grow (for instance by cross-jumping
|
instance by loop unrolling) or grow (for instance by cross-jumping
|
optimization), so scaling sometimes has to be performed multiple
|
optimization), so scaling sometimes has to be performed multiple
|
times.
|
times.
|
|
|
@findex gcov_type
|
@findex gcov_type
|
The @code{count} contains hard-counted numbers of execution measured
|
The @code{count} contains hard-counted numbers of execution measured
|
during training runs and is nonzero only when profile feedback is
|
during training runs and is nonzero only when profile feedback is
|
available. This value is represented as the host's widest integer
|
available. This value is represented as the host's widest integer
|
(typically a 64 bit integer) of the special type @code{gcov_type}.
|
(typically a 64 bit integer) of the special type @code{gcov_type}.
|
|
|
Most optimization passes can use only the frequency information of a
|
Most optimization passes can use only the frequency information of a
|
basic block, but a few passes may want to know hard execution counts.
|
basic block, but a few passes may want to know hard execution counts.
|
The frequencies should always match the counts after scaling, however
|
The frequencies should always match the counts after scaling, however
|
during updating of the profile information numerical error may
|
during updating of the profile information numerical error may
|
accumulate into quite large errors.
|
accumulate into quite large errors.
|
|
|
@findex REG_BR_PROB_BASE, EDGE_FREQUENCY
|
@findex REG_BR_PROB_BASE, EDGE_FREQUENCY
|
Each edge also contains a branch probability field: an integer in the
|
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
|
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
|
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
|
@code{dest} basic block, i.e.@: the probability that control will flow
|
along this edge. The @code{EDGE_FREQUENCY} macro is available to
|
along this edge. The @code{EDGE_FREQUENCY} macro is available to
|
compute how frequently a given edge is taken. There is a @code{count}
|
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
|
field for each edge as well, representing same information as for a
|
basic block.
|
basic block.
|
|
|
The basic block frequencies are not represented in the instruction
|
The basic block frequencies are not represented in the instruction
|
stream, but in the RTL representation the edge frequencies are
|
stream, but in the RTL representation the edge frequencies are
|
represented for conditional jumps (via the @code{REG_BR_PROB}
|
represented for conditional jumps (via the @code{REG_BR_PROB}
|
macro) since they are used when instructions are output to the
|
macro) since they are used when instructions are output to the
|
assembly file and the flow graph is no longer maintained.
|
assembly file and the flow graph is no longer maintained.
|
|
|
@cindex reverse probability
|
@cindex reverse probability
|
The probability that control flow arrives via a given edge to its
|
The probability that control flow arrives via a given edge to its
|
destination basic block is called @dfn{reverse probability} and is not
|
destination basic block is called @dfn{reverse probability} and is not
|
directly represented, but it may be easily computed from frequencies
|
directly represented, but it may be easily computed from frequencies
|
of basic blocks.
|
of basic blocks.
|
|
|
@findex redirect_edge_and_branch
|
@findex redirect_edge_and_branch
|
Updating profile information is a delicate task that can unfortunately
|
Updating profile information is a delicate task that can unfortunately
|
not be easily integrated with the CFG manipulation API@. Many of the
|
not be easily integrated with the CFG manipulation API@. Many of the
|
functions and hooks to modify the CFG, such as
|
functions and hooks to modify the CFG, such as
|
@code{redirect_edge_and_branch}, do not have enough information to
|
@code{redirect_edge_and_branch}, do not have enough information to
|
easily update the profile, so updating it is in the majority of cases
|
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
|
left up to the caller. It is difficult to uncover bugs in the profile
|
updating code, because they manifest themselves only by producing
|
updating code, because they manifest themselves only by producing
|
worse code, and checking profile consistency is not possible because
|
worse code, and checking profile consistency is not possible because
|
of numeric error accumulation. Hence special attention needs to be
|
of numeric error accumulation. Hence special attention needs to be
|
given to this issue in each pass that modifies the CFG@.
|
given to this issue in each pass that modifies the CFG@.
|
|
|
@findex REG_BR_PROB_BASE, BB_FREQ_BASE, count
|
@findex REG_BR_PROB_BASE, BB_FREQ_BASE, count
|
It is important to point out that @code{REG_BR_PROB_BASE} and
|
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
|
@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
|
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
|
not possible to even square the @code{count} field, as modern CPUs are
|
fast enough to execute $2^32$ operations quickly.
|
fast enough to execute $2^32$ operations quickly.
|
|
|
|
|
@node Maintaining the CFG
|
@node Maintaining the CFG
|
@section Maintaining the CFG
|
@section Maintaining the CFG
|
@findex cfghooks.h
|
@findex cfghooks.h
|
|
|
An important task of each compiler pass is to keep both the control
|
An important task of each compiler pass is to keep both the control
|
flow graph and all profile information up-to-date. Reconstruction of
|
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
|
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
|
very expensive and lost profile information cannot be reconstructed at
|
all.
|
all.
|
|
|
GCC has two major intermediate representations, and both use the
|
GCC has two major intermediate representations, and both use the
|
@code{basic_block} and @code{edge} data types to represent control
|
@code{basic_block} and @code{edge} data types to represent control
|
flow. Both representations share as much of the CFG maintenance code
|
flow. Both representations share as much of the CFG maintenance code
|
as possible. For each representation, a set of @dfn{hooks} is defined
|
as possible. For each representation, a set of @dfn{hooks} is defined
|
so that each representation can provide its own implementation of CFG
|
so that each representation can provide its own implementation of CFG
|
manipulation routines when necessary. These hooks are defined in
|
manipulation routines when necessary. These hooks are defined in
|
@file{cfghooks.h}. There are hooks for almost all common CFG
|
@file{cfghooks.h}. There are hooks for almost all common CFG
|
manipulations, including block splitting and merging, edge redirection
|
manipulations, including block splitting and merging, edge redirection
|
and creating and deleting basic blocks. These hooks should provide
|
and creating and deleting basic blocks. These hooks should provide
|
everything you need to maintain and manipulate the CFG in both the RTL
|
everything you need to maintain and manipulate the CFG in both the RTL
|
and @code{tree} representation.
|
and @code{tree} representation.
|
|
|
At the moment, the basic block boundaries are maintained transparently
|
At the moment, the basic block boundaries are maintained transparently
|
when modifying instructions, so there rarely is a need to move them
|
when modifying instructions, so there rarely is a need to move them
|
manually (such as in case someone wants to output instruction outside
|
manually (such as in case someone wants to output instruction outside
|
basic block explicitly).
|
basic block explicitly).
|
Often the CFG may be better viewed as integral part of instruction
|
Often the CFG may be better viewed as integral part of instruction
|
chain, than structure built on the top of it. However, in principle
|
chain, than structure built on the top of it. However, in principle
|
the control flow graph for the @code{tree} representation is
|
the control flow graph for the @code{tree} representation is
|
@emph{not} an integral part of the representation, in that a function
|
@emph{not} an integral part of the representation, in that a function
|
tree may be expanded without first building a flow graph for the
|
tree may be expanded without first building a flow graph for the
|
@code{tree} representation at all. This happens when compiling
|
@code{tree} representation at all. This happens when compiling
|
without any @code{tree} optimization enabled. When the @code{tree}
|
without any @code{tree} optimization enabled. When the @code{tree}
|
optimizations are enabled and the instruction stream is rewritten in
|
optimizations are enabled and the instruction stream is rewritten in
|
SSA form, the CFG is very tightly coupled with the instruction stream.
|
SSA form, the CFG is very tightly coupled with the instruction stream.
|
In particular, statement insertion and removal has to be done with
|
In particular, statement insertion and removal has to be done with
|
care. In fact, the whole @code{tree} representation can not be easily
|
care. In fact, the whole @code{tree} representation can not be easily
|
used or maintained without proper maintenance of the CFG
|
used or maintained without proper maintenance of the CFG
|
simultaneously.
|
simultaneously.
|
|
|
@findex BLOCK_FOR_INSN, bb_for_stmt
|
@findex BLOCK_FOR_INSN, bb_for_stmt
|
In the RTL representation, each instruction has a
|
In the RTL representation, each instruction has a
|
@code{BLOCK_FOR_INSN} value that represents pointer to the basic block
|
@code{BLOCK_FOR_INSN} value that represents pointer to the basic block
|
that contains the instruction. In the @code{tree} representation, the
|
that contains the instruction. In the @code{tree} representation, the
|
function @code{bb_for_stmt} returns a pointer to the basic block
|
function @code{bb_for_stmt} returns a pointer to the basic block
|
containing the queried statement.
|
containing the queried statement.
|
|
|
@cindex block statement iterators
|
@cindex block statement iterators
|
When changes need to be applied to a function in its @code{tree}
|
When changes need to be applied to a function in its @code{tree}
|
representation, @dfn{block statement iterators} should be used. These
|
representation, @dfn{block statement iterators} should be used. These
|
iterators provide an integrated abstraction of the flow graph and the
|
iterators provide an integrated abstraction of the flow graph and the
|
instruction stream. Block statement iterators are constructed using
|
instruction stream. Block statement iterators are constructed using
|
the @code{block_stmt_iterator} data structure and several modifier are
|
the @code{block_stmt_iterator} data structure and several modifier are
|
available, including the following:
|
available, including the following:
|
|
|
@ftable @code
|
@ftable @code
|
@item bsi_start
|
@item bsi_start
|
This function initializes a @code{block_stmt_iterator} that points to
|
This function initializes a @code{block_stmt_iterator} that points to
|
the first non-empty statement in a basic block.
|
the first non-empty statement in a basic block.
|
|
|
@item bsi_last
|
@item bsi_last
|
This function initializes a @code{block_stmt_iterator} that points to
|
This function initializes a @code{block_stmt_iterator} that points to
|
the last statement in a basic block.
|
the last statement in a basic block.
|
|
|
@item bsi_end_p
|
@item bsi_end_p
|
This predicate is @code{true} if a @code{block_stmt_iterator}
|
This predicate is @code{true} if a @code{block_stmt_iterator}
|
represents the end of a basic block.
|
represents the end of a basic block.
|
|
|
@item bsi_next
|
@item bsi_next
|
This function takes a @code{block_stmt_iterator} and makes it point to
|
This function takes a @code{block_stmt_iterator} and makes it point to
|
its successor.
|
its successor.
|
|
|
@item bsi_prev
|
@item bsi_prev
|
This function takes a @code{block_stmt_iterator} and makes it point to
|
This function takes a @code{block_stmt_iterator} and makes it point to
|
its predecessor.
|
its predecessor.
|
|
|
@item bsi_insert_after
|
@item bsi_insert_after
|
This function inserts a statement after the @code{block_stmt_iterator}
|
This function inserts a statement after the @code{block_stmt_iterator}
|
passed in. The final parameter determines whether the statement
|
passed in. The final parameter determines whether the statement
|
iterator is updated to point to the newly inserted statement, or left
|
iterator is updated to point to the newly inserted statement, or left
|
pointing to the original statement.
|
pointing to the original statement.
|
|
|
@item bsi_insert_before
|
@item bsi_insert_before
|
This function inserts a statement before the @code{block_stmt_iterator}
|
This function inserts a statement before the @code{block_stmt_iterator}
|
passed in. The final parameter determines whether the statement
|
passed in. The final parameter determines whether the statement
|
iterator is updated to point to the newly inserted statement, or left
|
iterator is updated to point to the newly inserted statement, or left
|
pointing to the original statement.
|
pointing to the original statement.
|
|
|
@item bsi_remove
|
@item bsi_remove
|
This function removes the @code{block_stmt_iterator} passed in and
|
This function removes the @code{block_stmt_iterator} passed in and
|
rechains the remaining statements in a basic block, if any.
|
rechains the remaining statements in a basic block, if any.
|
@end ftable
|
@end ftable
|
|
|
@findex BB_HEAD, BB_END
|
@findex BB_HEAD, BB_END
|
In the RTL representation, the macros @code{BB_HEAD} and @code{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
|
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
|
abstract iterators are defined for traversing the insn chain, but you
|
can just use @code{NEXT_INSN} and @code{PREV_INSN} instead. See
|
can just use @code{NEXT_INSN} and @code{PREV_INSN} instead. See
|
@xref{Insns}.
|
@xref{Insns}.
|
|
|
@findex purge_dead_edges
|
@findex purge_dead_edges
|
Usually a code manipulating pass simplifies the instruction stream and
|
Usually a code manipulating pass simplifies the instruction stream and
|
the flow of control, possibly eliminating some edges. This may for
|
the flow of control, possibly eliminating some edges. This may for
|
example happen when a conditional jump is replaced with an
|
example happen when a conditional jump is replaced with an
|
unconditional jump, but also when simplifying possibly trapping
|
unconditional jump, but also when simplifying possibly trapping
|
instruction to non-trapping while compiling Java. Updating of edges
|
instruction to non-trapping while compiling Java. Updating of edges
|
is not transparent and each optimization pass is required to do so
|
is not transparent and each optimization pass is required to do so
|
manually. However only few cases occur in practice. The pass may
|
manually. However only few cases occur in practice. The pass may
|
call @code{purge_dead_edges} on a given basic block to remove
|
call @code{purge_dead_edges} on a given basic block to remove
|
superfluous edges, if any.
|
superfluous edges, if any.
|
|
|
@findex redirect_edge_and_branch, redirect_jump
|
@findex redirect_edge_and_branch, redirect_jump
|
Another common scenario is redirection of branch instructions, but
|
Another common scenario is redirection of branch instructions, but
|
this is best modeled as redirection of edges in the control flow graph
|
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
|
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
|
low level functions, such as @code{redirect_jump} that operate on RTL
|
chain only. The CFG hooks defined in @file{cfghooks.h} should provide
|
chain only. The CFG hooks defined in @file{cfghooks.h} should provide
|
the complete API required for manipulating and maintaining the CFG@.
|
the complete API required for manipulating and maintaining the CFG@.
|
|
|
@findex split_block
|
@findex split_block
|
It is also possible that a pass has to insert control flow instruction
|
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
|
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
|
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
|
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
|
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
|
when an instruction in the middle of a basic block has to become the
|
target of a jump or branch instruction.
|
target of a jump or branch instruction.
|
|
|
@findex insert_insn_on_edge
|
@findex insert_insn_on_edge
|
@findex commit_edge_insertions
|
@findex commit_edge_insertions
|
@findex bsi_insert_on_edge
|
@findex bsi_insert_on_edge
|
@findex bsi_commit_edge_inserts
|
@findex bsi_commit_edge_inserts
|
@cindex edge splitting
|
@cindex edge splitting
|
For a global optimizer, a common operation is to split edges in the
|
For a global optimizer, a common operation is to split edges in the
|
flow graph and insert instructions on them. In the RTL
|
flow graph and insert instructions on them. In the RTL
|
representation, this can be easily done using the
|
representation, this can be easily done using the
|
@code{insert_insn_on_edge} function that emits an instruction
|
@code{insert_insn_on_edge} function that emits an instruction
|
``on the edge'', caching it for a later @code{commit_edge_insertions}
|
``on the edge'', caching it for a later @code{commit_edge_insertions}
|
call that will take care of moving the inserted instructions off the
|
call that will take care of moving the inserted instructions off the
|
edge into the instruction stream contained in a basic block. This
|
edge into the instruction stream contained in a basic block. This
|
includes the creation of new basic blocks where needed. In the
|
includes the creation of new basic blocks where needed. In the
|
@code{tree} representation, the equivalent functions are
|
@code{tree} representation, the equivalent functions are
|
@code{bsi_insert_on_edge} which inserts a block statement
|
@code{bsi_insert_on_edge} which inserts a block statement
|
iterator on an edge, and @code{bsi_commit_edge_inserts} which flushes
|
iterator on an edge, and @code{bsi_commit_edge_inserts} which flushes
|
the instruction to actual instruction stream.
|
the instruction to actual instruction stream.
|
|
|
While debugging the optimization pass, a @code{verify_flow_info}
|
While debugging the optimization pass, a @code{verify_flow_info}
|
function may be useful to find bugs in the control flow graph updating
|
function may be useful to find bugs in the control flow graph updating
|
code.
|
code.
|
|
|
Note that at present, the representation of control flow in the
|
Note that at present, the representation of control flow in the
|
@code{tree} representation is discarded before expanding to RTL@.
|
@code{tree} representation is discarded before expanding to RTL@.
|
Long term the CFG should be maintained and ``expanded'' to the
|
Long term the CFG should be maintained and ``expanded'' to the
|
RTL representation along with the function @code{tree} itself.
|
RTL representation along with the function @code{tree} itself.
|
|
|
|
|
@node Liveness information
|
@node Liveness information
|
@section Liveness information
|
@section Liveness information
|
@cindex Liveness representation
|
@cindex Liveness representation
|
Liveness information is useful to determine whether some register is
|
Liveness information is useful to determine whether some register is
|
``live'' at given point of program, i.e.@: that it contains a value that
|
``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
|
may be used at a later point in the program. This information is
|
used, for instance, during register allocation, as the pseudo
|
used, for instance, during register allocation, as the pseudo
|
registers only need to be assigned to a unique hard register or to a
|
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
|
stack slot if they are live. The hard registers and stack slots may
|
be freely reused for other values when a register is dead.
|
be freely reused for other values when a register is dead.
|
|
|
Liveness information is available in the back end starting with
|
Liveness information is available in the back end starting with
|
@code{pass_df_initialize} and ending with @code{pass_df_finish}. Three
|
@code{pass_df_initialize} and ending with @code{pass_df_finish}. Three
|
flavors of live analysis are available: With @code{LR}, it is possible
|
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
|
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
|
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
|
@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.
|
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
|
@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
|
variable is live at @code{P} if there is both an assignment that reaches
|
it from the beginning of the function and a use that can be reached on
|
it from the beginning of the function and a use that can be reached on
|
some path from @code{P} to the end of the function.
|
some path from @code{P} to the end of the function.
|
|
|
In general @code{LIVE} is the most useful of the three. The macros
|
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.
|
@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
|
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
|
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
|
date after calls are made to @code{df_analyze}. See the file
|
@code{df-core.c} for details on using the dataflow.
|
@code{df-core.c} for details on using the dataflow.
|
|
|
|
|
@findex REG_DEAD, REG_UNUSED
|
@findex REG_DEAD, REG_UNUSED
|
The liveness information is stored partly in the RTL instruction stream
|
The liveness information is stored partly in the RTL instruction stream
|
and partly in the flow graph. Local information is stored in the
|
and partly in the flow graph. Local information is stored in the
|
instruction stream: Each instruction may contain @code{REG_DEAD} notes
|
instruction stream: Each instruction may contain @code{REG_DEAD} notes
|
representing that the value of a given register is no longer needed, or
|
representing that the value of a given register is no longer needed, or
|
@code{REG_UNUSED} notes representing that the value computed by the
|
@code{REG_UNUSED} notes representing that the value computed by the
|
instruction is never used. The second is useful for instructions
|
instruction is never used. The second is useful for instructions
|
computing multiple values at once.
|
computing multiple values at once.
|
|
|
|
|
