aboutsummaryrefslogtreecommitdiff
path: root/gcc/doc/cfg.texi
diff options
context:
space:
mode:
authorMartin Liska <mliska@suse.cz>2022-11-07 13:23:41 +0100
committerMartin Liska <mliska@suse.cz>2022-11-09 09:00:35 +0100
commit54ca4eef58661a7d7a511e2bbbe309bde1732abf (patch)
tree4f9067b036a4e7c08d0d483246cb5ab5a0d60d41 /gcc/doc/cfg.texi
parent564a805f9f08b4346a854ab8dca2e5b561a7a28e (diff)
downloadgcc-54ca4eef58661a7d7a511e2bbbe309bde1732abf.zip
gcc-54ca4eef58661a7d7a511e2bbbe309bde1732abf.tar.gz
gcc-54ca4eef58661a7d7a511e2bbbe309bde1732abf.tar.bz2
sphinx: remove texinfo files
gcc/d/ChangeLog: * gdc.texi: Removed. gcc/ChangeLog: * doc/analyzer.texi: Removed. * doc/avr-mmcu.texi: Removed. * doc/bugreport.texi: Removed. * doc/cfg.texi: Removed. * doc/collect2.texi: Removed. * doc/compat.texi: Removed. * doc/configfiles.texi: Removed. * doc/configterms.texi: Removed. * doc/contrib.texi: Removed. * doc/contribute.texi: Removed. * doc/cpp.texi: Removed. * doc/cppdiropts.texi: Removed. * doc/cppenv.texi: Removed. * doc/cppinternals.texi: Removed. * doc/cppopts.texi: Removed. * doc/cppwarnopts.texi: Removed. * doc/extend.texi: Removed. * doc/fragments.texi: Removed. * doc/frontends.texi: Removed. * doc/gcc.texi: Removed. * doc/gccint.texi: Removed. * doc/gcov-dump.texi: Removed. * doc/gcov-tool.texi: Removed. * doc/gcov.texi: Removed. * doc/generic.texi: Removed. * doc/gimple.texi: Removed. * doc/gnu.texi: Removed. * doc/gty.texi: Removed. * doc/headerdirs.texi: Removed. * doc/hostconfig.texi: Removed. * doc/implement-c.texi: Removed. * doc/implement-cxx.texi: Removed. * doc/include/fdl.texi: Removed. * doc/include/funding.texi: Removed. * doc/include/gcc-common.texi: Removed. * doc/include/gpl_v3.texi: Removed. * doc/install.texi: Removed. * doc/interface.texi: Removed. * doc/invoke.texi: Removed. * doc/languages.texi: Removed. * doc/libgcc.texi: Removed. * doc/loop.texi: Removed. * doc/lto-dump.texi: Removed. * doc/lto.texi: Removed. * doc/makefile.texi: Removed. * doc/match-and-simplify.texi: Removed. * doc/md.texi: Removed. * doc/objc.texi: Removed. * doc/optinfo.texi: Removed. * doc/options.texi: Removed. * doc/passes.texi: Removed. * doc/plugins.texi: Removed. * doc/poly-int.texi: Removed. * doc/portability.texi: Removed. * doc/rtl.texi: Removed. * doc/service.texi: Removed. * doc/sourcebuild.texi: Removed. * doc/standards.texi: Removed. * doc/tm.texi: Removed. * doc/tree-ssa.texi: Removed. * doc/trouble.texi: Removed. * doc/ux.texi: Removed. * doc/tm.texi.in: Removed. gcc/fortran/ChangeLog: * gfc-internals.texi: Removed. * gfortran.texi: Removed. * intrinsic.texi: Removed. * invoke.texi: Removed. gcc/go/ChangeLog: * gccgo.texi: Removed. libgomp/ChangeLog: * libgomp.texi: Removed. libiberty/ChangeLog: * at-file.texi: Removed. * copying-lib.texi: Removed. * functions.texi: Removed. * libiberty.texi: Removed. * obstacks.texi: Removed. libitm/ChangeLog: * libitm.texi: Removed. libquadmath/ChangeLog: * libquadmath.texi: Removed.
Diffstat (limited to 'gcc/doc/cfg.texi')
-rw-r--r--gcc/doc/cfg.texi684
1 files changed, 0 insertions, 684 deletions
diff --git a/gcc/doc/cfg.texi b/gcc/doc/cfg.texi
deleted file mode 100644
index 32aacdd..0000000
--- a/gcc/doc/cfg.texi
+++ /dev/null
@@ -1,684 +0,0 @@
-@c -*-texinfo-*-
-@c Copyright (C) 2001-2022 Free Software 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{GIMPLE} 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}.
-
-In GCC, the representation of control flow is maintained throughout
-the compilation process, from constructing the CFG early in
-@code{pass_build_cfg} to @code{pass_free_cfg} (see @file{passes.def}).
-The CFG takes various different modes and may undergo extensive
-manipulations, but the graph is always valid between its construction
-and its release. This way, transfer of information such as data flow,
-a measured profile, or the loop tree, can be propagated through the
-passes pipeline, and even from @code{GIMPLE} to @code{RTL}.
-
-Often the CFG may be better viewed as integral part of instruction
-chain, than structure built on the top of it. Updating the compiler's
-intermediate representation for instructions cannot be easily done
-without proper maintenance of the CFG simultaneously.
-
-@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 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.
-
-@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}. The indices 0 and 1 are special codes
-reserved for @code{ENTRY_BLOCK} and @code{EXIT_BLOCK}, the
-indices of @code{ENTRY_BLOCK_PTR} and @code{EXIT_BLOCK_PTR}.
-
-@findex next_bb, prev_bb, FOR_EACH_BB, FOR_ALL_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, except @code{ENTRY_BLOCK} and @code{EXIT_BLOCK}.
-The macro @code{FOR_ALL_BB} also visits all basic blocks in
-lexicographical order, including @code{ENTRY_BLOCK} and @code{EXIT_BLOCK}.
-
-@findex post_order_compute, inverted_post_order_compute, walk_dominator_tree
-The functions @code{post_order_compute} and @code{inverted_post_order_compute}
-can be used to compute topological orders of the CFG. The orders are
-stored as vectors of basic block indices. The @code{BASIC_BLOCK} array
-can be used to iterate each basic block by index.
-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@.
-
-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{GIMPLE}
-and RTL), there are pointers to the head and end of a basic block for
-both representations, stored in intermediate representation specific
-data in the @code{il} field of @code{struct basic_block_def}.
-
-@findex CODE_LABEL
-@findex NOTE_INSN_BASIC_BLOCK
-For RTL, these pointers are @code{BB_HEAD} and @code{BB_END}.
-
-@cindex insn notes, notes
-@findex NOTE_INSN_BASIC_BLOCK
-In the RTL representation of a function, the instruction stream
-contains not only the ``real'' instructions, but also @dfn{notes}
-or @dfn{insn notes} (to distinguish them from @dfn{reg 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, so updating
-can sometimes be tedious. All types of insn notes are defined
-in @file{insn-notes.def}.
-
-In the RTL function representation, the instructions contained in a
-basic block always follow a @code{NOTE_INSN_BASIC_BLOCK}, but zero
-or more @code{CODE_LABEL} nodes can precede the block note.
-A basic block ends with a control flow instruction or with the last
-instruction before the next @code{CODE_LABEL} or
-@code{NOTE_INSN_BASIC_BLOCK}.
-By definition, a @code{CODE_LABEL} cannot appear in the middle of
-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 GIMPLE statement iterators
-For the @code{GIMPLE} representation, the PHI nodes and statements
-contained in a basic block are in a @code{gimple_seq} pointed to by
-the basic block intermediate language specific pointers.
-Abstract containers and iterators are used to access the PHI nodes
-and statements in a basic blocks. These iterators are called
-@dfn{GIMPLE statement iterators} (GSIs). Grep for @code{^gsi}
-in the various @file{gimple-*} and @file{tree-*} files.
-There is a @code{gimple_stmt_iterator} type for iterating over
-all kinds of statement, and a @code{gphi_iterator} subclass for
-iterating over PHI nodes.
-The following snippet will pretty-print all PHI nodes the statements
-of the current function in the GIMPLE representation.
-
-@smallexample
-basic_block bb;
-
-FOR_EACH_BB (bb)
- @{
- gphi_iterator pi;
- gimple_stmt_iterator si;
-
- for (pi = gsi_start_phis (bb); !gsi_end_p (pi); gsi_next (&pi))
- @{
- gphi *phi = pi.phi ();
- print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
- @}
- for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
- @{
- gimple stmt = gsi_stmt (si);
- print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
- @}
- @}
-@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_edge
-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
-Ada 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{GIMPLE} 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
-
-@findex pass_duplicate_computed_gotos
-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
-(in the pass called @code{pass_duplicate_computed_gotos}).
-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{GIMPLE} 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{GIMPLE} 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).
-
-@findex BLOCK_FOR_INSN, gimple_bb
-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{GIMPLE} representation, the
-function @code{gimple_bb} returns a pointer to the basic block
-containing the queried statement.
-
-@cindex GIMPLE statement iterators
-When changes need to be applied to a function in its @code{GIMPLE}
-representation, @dfn{GIMPLE 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{gimple_stmt_iterator} data structure and several modifiers are
-available, including the following:
-
-@ftable @code
-@item gsi_start
-This function initializes a @code{gimple_stmt_iterator} that points to
-the first non-empty statement in a basic block.
-
-@item gsi_last
-This function initializes a @code{gimple_stmt_iterator} that points to
-the last statement in a basic block.
-
-@item gsi_end_p
-This predicate is @code{true} if a @code{gimple_stmt_iterator}
-represents the end of a basic block.
-
-@item gsi_next
-This function takes a @code{gimple_stmt_iterator} and makes it point to
-its successor.
-
-@item gsi_prev
-This function takes a @code{gimple_stmt_iterator} and makes it point to
-its predecessor.
-
-@item gsi_insert_after
-This function inserts a statement after the @code{gimple_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 gsi_insert_before
-This function inserts a statement before the @code{gimple_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 gsi_remove
-This function removes the @code{gimple_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. @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. 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 gsi_insert_on_edge
-@findex gsi_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{GIMPLE} representation, the equivalent functions are
-@code{gsi_insert_on_edge} which inserts a block statement
-iterator on an edge, and @code{gsi_commit_edge_inserts} which flushes
-the instruction to actual instruction stream.
-
-@findex verify_flow_info
-@cindex CFG verification
-While debugging the optimization pass, the @code{verify_flow_info}
-function may be useful to find bugs in the control flow graph updating
-code.
-
-
-@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 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.cc} 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.
-