diff options
author | Martin Liska <mliska@suse.cz> | 2022-11-07 13:23:41 +0100 |
---|---|---|
committer | Martin Liska <mliska@suse.cz> | 2022-11-09 09:00:35 +0100 |
commit | 54ca4eef58661a7d7a511e2bbbe309bde1732abf (patch) | |
tree | 4f9067b036a4e7c08d0d483246cb5ab5a0d60d41 /gcc/doc/cfg.texi | |
parent | 564a805f9f08b4346a854ab8dca2e5b561a7a28e (diff) | |
download | gcc-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.texi | 684 |
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. - |