@c -*-texinfo-*-
-@c Copyright (C) 2001, 2003, 2004 Free Software Foundation, Inc.
+@c Copyright (C) 2001, 2003, 2004, 2005 Free Software Foundation, Inc.
@c This is part of the GCC manual.
@c For copying conditions, see the file gcc.texi.
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
+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.
+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
@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
+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{pred} and @code{succ} of the @code{basic_block} data
-type point to singly linked lists of edges to the predecessors and
-successors of the block. The edges are linked via the
-@code{succ_next} and @code{pred_next} members of the @code{edge} data
-type.
+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
@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
+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
@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
+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
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}
+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.
@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
+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
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.
+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
constructed using the @code{block_stmt_iterator} data structure and
several modifier are available, including the following:
-@table @code
+@ftable @code
@item bsi_start
-@findex 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
-@findex bsi_last
This function initializes a @code{block_stmt_iterator} that points to
the last statement in a basic block.
@item bsi_end_p
-@findex bsi_end_p
This predicate is @code{true} if a @code{block_stmt_iterator}
represents the end of a basic block.
@item bsi_next
-@findex bsi_next
This function takes a @code{block_stmt_iterator} and makes it point to
its successor.
@item bsi_prev
-@item bsi_prev
This function takes a @code{block_stmt_iterator} and makes it point to
its predecessor.
@item bsi_insert_after
-@findex 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
-@findex 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
@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 table
+@end ftable
@findex BB_HEAD, BB_END
In the RTL representation, the macros @code{BB_HEAD} and @code{BB_END}
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.
+the complete API required for manipulating and maintaining the CFG@.
-@findex find_sub_basic_blocks, split_block
+@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. In the RTL representation, the
-@code{find_sub_basic_blocks} may be used to split existing basic block
-and add necessary edges. 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
target of a jump or branch instruction.
-@findex insert_insn_on_edge, commit_edge_insertions
-@findex bsi_insert_on_edge, bsi_commit_edge_inserts
+@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
code.
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
RTL representation along with the function @code{tree} itself.