@c -*-texinfo-*-
-@c Copyright (C) 2001, 2003, 2004 Free Software Foundation, Inc.
+@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.
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
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,
+series of jumps,
@smallexample
goto *x;
- [ ... ]
+ [ @dots{} ]
goto *x;
- [ ... ]
+ [ @dots{} ]
goto *x;
- [ ... ]
+ [ @dots{} ]
@end smallexample
@noindent
@smallexample
goto y;
- [ ... ]
+ [ @dots{} ]
goto y;
- [ ... ]
+ [ @dots{} ]
goto y;
- [ ... ]
+ [ @dots{} ]
y:
goto *x;
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
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:
+instruction stream. Block statement iterators are 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}
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}.
+can just use @code{NEXT_INSN} and @code{PREV_INSN} instead. @xref{Insns}.
@findex purge_dead_edges
Usually a code manipulating pass simplifies the instruction stream and
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
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}
+While debugging the optimization pass, a @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.
+@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.
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 use 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
+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.
-@findex global_live_at_start, global_live_at_end
-Global liveness information is stored in the control flow graph.
-Each basic block contains two bitmaps, @code{global_live_at_start} and
-@code{global_live_at_end} representing liveness of each register at
-the entry and exit of the basic block. The file @code{flow.c}
-contains functions to compute liveness of each register at any given
-place in the instruction stream using this information.
-
-@findex BB_DIRTY, clear_bb_flags, update_life_info_in_dirty_blocks
-Liveness is expensive to compute and thus it is desirable to keep it
-up to date during code modifying passes. This can be easily
-accomplished using the @code{flags} field of a basic block. Functions
-modifying the instruction stream automatically set the @code{BB_DIRTY}
-flag of a modifies basic block, so the pass may simply
-use@code{clear_bb_flags} before doing any modifications and then ask
-the data flow module to have liveness updated via the
-@code{update_life_info_in_dirty_blocks} function.
-
-This scheme works reliably as long as no control flow graph
-transformations are done. The task of updating liveness after control
-flow graph changes is more difficult as normal iterative data flow
-analysis may produce invalid results or get into an infinite cycle
-when the initial solution is not below the desired one. Only simple
-transformations, like splitting basic blocks or inserting on edges,
-are safe, as functions to implement them already know how to update
-liveness information locally.
OSDN Git Service
