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