@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.
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
@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;
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
-@findex 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}
chain only. The CFG hooks defined in @file{cfghooks.h} should provide
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.
used, for instance, during register allocation, as the pseudo
registers only need to be assigned to a unique hard register or to a
stack slot if they are live. The hard registers and stack slots may
-be freely reused for other values when a register is dead.
+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
