This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[tree-ssa] cfg.texi needs reviewing by a native speaker (Was: Re: "Documentation by paper")


On Wednesday 04 February 2004 20:09, Robert Dewar wrote:
> Joe Buck wrote:
> > OK, the *best* would be written by that almost non-existent programmer
> > who combines a love of writing clear English prose with the extraordinary
> > discipline required to do it first and keep it current.  But since this
> > species is almost non-existent, you need to read my phrase "best
> > documentation" for "best documentation achievable in practice".
>
> You are FAR too pessimistic, I know lots of programmers who meet
> these criteria.

I most certainly don't qualify for Joe's description.  I'm sure one
of you does, and since part of this discussion was about documenting
what a basic block is, I kindly ask you, as native speakers who care
about good documentation, to review this new chapter for the manual.

It's based on Jan Hubicka's old cfg.texi, which he&others wrote after
doing a lot of work on the CFG representation in GCC.  That document
is almost three years old now, but it was never reviewed (not even by
the people in this thread who say they care about documentation).  I
don't claim it's perfect -- on the contrary.  But does it look like
an acceptable start?

Thanks,

Gr.
Steven

doc/
	* cfg.texi: New chapter for the internals manual.  Briefly describes
	the data structures used to represent the control flow graph, and
	the issues and API to modify and maintain the CFG.
Index: doc/cfg.texi
===================================================================
RCS file: doc/cfg.texi
diff -N doc/cfg.texi
*** /dev/null	1 Jan 1970 00:00:00 -0000
--- doc/cfg.texi	4 Feb 2004 19:54:37 -0000
***************
*** 0 ****
--- 1,597 ----
+ @c -*-texinfo-*-
+ @c Copyright (C) 2001, 2003, 2004 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{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
+ transparenly by the provided API for manupulating the CFG.  The macro
+ @code{FOR_EACH_BB} can be used to visit all this order.
+ 
+ @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 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.
+ 
+ 
+ @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{pred} and @code{succ} of the @code{basic_block} data
+ type point to single linked lists of edges to the predecessors and
+ successorts of the block.  The edges are linked via the
+ @code{succ_next} and @code{pred_next} members of the @code{edge} data
+ type.
+ 
+ @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, 
+ 
+ @example
+   goto *x;
+   [ ... ]
+ 
+   goto *x;
+   [ ... ]
+ 
+   goto *x;
+   [ ... ]
+ @end example
+ 
+ @noindent
+ factoring the computed jumps results in the following code sequence
+ which has a much simpler flow graph:
+ 
+ @example
+   goto y;
+   [ ... ]
+ 
+   goto y;
+   [ ... ]
+ 
+   goto y;
+   [ ... ]
+ 
+ y:
+   goto *x;
+ @end example
+ 
+ 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 maintainance 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 buildint 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 maintainance 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 iterators are
+ constructed using the @code{block_stmt_iterator} data structure and
+ several modifier are available, including the following:
+ 
+ @table @code
+ @item bsi_start
+ @findex bsi_start
+ This function initializes a @code{block_stmt_iterator} that points to
+ the first non-empty statement in a basic block.
+ 
+ @item bsi_last
+ @findex bsi_last
+ This function initializes a @code{block_stmt_iterator} that points to
+ the last statement in a basic block.
+ 
+ @item bsi_end_p
+ @findex bsi_end_p
+ This predicate is @code{true} if a @code{block_stmt_iterator}
+ represents the end of a basic block.
+ 
+ @item bsi_next
+ @findex bsi_next
+ This function takes a @code{block_stmt_iterator} and makes it point to
+ its successor.
+ 
+ @item bsi_prev
+ @item bsi_prev
+ This function takes a @code{block_stmt_iterator} and makes it point to
+ its predecessor.
+ 
+ @item bsi_insert_after
+ @findex bsi_insert_after
+ This function inserts a statement after the @code{block_stmt_iterator}
+ passed in.  The final parameter determines whether the statement
+ iterator is updated to point to the newly inserted statement, or left
+ pointing to the original statement.
+ 
+ @item bsi_insert_before
+ @findex bsi_insert_before
+ This function inserts a statement before the @code{block_stmt_iterator}
+ passed in.  The final parameter determines whether the statement
+ iterator is updated to point to the newly inserted statement, or left
+ 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 table
+ 
+ @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 insns 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 find_sub_basic_blocks, 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 defintion: The
+ block must be split to make sure it only has one entry point, i.e. the
+ head of the basic block.  In the RTL representation, the
+ @code{find_sub_basic_blocks} may be used to split existing basic block
+ and add necessary edges.  The CFG hook @code{split_block} may be used
+ when an instruction in the middle of a basic block has to become the
+ target of a jump or branch instruction.
+ 
+ @findex insert_insn_on_edge, commit_edge_insertions
+ @findex bsi_insert_on_edge, bsi_commit_edge_inserts
+ @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.
+ 
+ @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.
+ 
+ @findex global_live_at_start, global_live_at_end
+ Global liveness information is stored in the control flow graph.
+ Each basic block contains two bitmaps, @code{global_live_at_start} and
+ @code{global_live_at_end} representing liveness of each register at
+ the entry and exit of the basic block.  The file @code{flow.c}
+ contains functions to compute liveness of each register at any given
+ place in the instruction stream using this information.
+ 
+ @findex BB_DIRTY, clear_bb_flags, update_life_info_in_dirty_blocks
+ Liveness is expensive to compute and thus it is desirable to keep it
+ up to date during code modifying passes.  This can be easily
+ accomplished using the @code{flags} field of a basic block.  Functions
+ modifying the instruction stream automatically set the @code{BB_DIRTY}
+ flag of a modifies basic block, so the pass may simply
+ use@code{clear_bb_flags} before doing any modifications and then ask
+ the dataflow modulule to have liveness updated via the
+ @code{update_life_info_in_dirty_blocks} function.
+ 
+ This scheme works reliably as long as no control flow graph
+ transformations are done.  The task of updating liveness after control
+ flow graph changes is more difficult as normal iterative data flow
+ analysis may produce invalid results or get into an infinite cycle
+ when the initial solution is not below the desired one.  Only simple
+ transformations, like splitting basic blocks or inserting on edges,
+ are safe, as functions to implement them already know how to update
+ liveness information locally.
Index: doc/gccint.texi
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doc/gccint.texi,v
retrieving revision 1.5.2.5
diff -c -3 -p -r1.5.2.5 gccint.texi
*** doc/gccint.texi	3 Jan 2004 23:03:21 -0000	1.5.2.5
--- doc/gccint.texi	4 Feb 2004 19:54:37 -0000
*************** Additional tutorial information is linke
*** 140,145 ****
--- 140,146 ----
  * Passes::          Order of passes, what they do, and what each file is for.
  * Trees::           The source representation used by the C and C++ front ends.
  * RTL::             The intermediate representation that most passes work on.
+ * Control Flow::    Maintaining and manipulating the control flow graph.
  * Machine Desc::    How to write machine description instruction patterns.
  * Target Macros::   How to write the machine description C macros and functions.
  * Host Config::     Writing the @file{xm-@var{machine}.h} file.
*************** Additional tutorial information is linke
*** 169,174 ****
--- 170,176 ----
  @include passes.texi
  @include c-tree.texi
  @include rtl.texi
+ @include cfg.texi
  @include md.texi
  @include tm.texi
  @include hostconfig.texi


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]