Control Flow Graph
******************

A control flow graph (CFG) is a data structure built on top of the intermediate code representation (the RTL or 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 basic-block.h.

Basic Blocks
============

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 basic_block data type.

Two pointer members of the basic_block structure are the pointers next_bb and 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 FOR_EACH_BB can be used to visit all the basic blocks in lexicographical order.  Dominator traversals are also possible using walk_dominator_tree.  Given two basic blocks A and B, block A dominates block B if A is always executed before B.

The BASIC_BLOCK array contains all basic blocks in an unspecified order.  Each basic_block structure has a field that holds a unique integer identifier index that is the index of the block in the BASIC_BLOCK array. The total number of basic blocks in the function is 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 last_basic_block.

Special basic blocks represent possible entry and exit points of a function.  These blocks are called ENTRY_BLOCK_PTR and EXIT_BLOCK_PTR.  These blocks do not contain any code, and are not elements of the BASIC_BLOCK array.  Therefore they have been assigned unique, negative index numbers.

Each basic_block also contains pointers to the first instruction (the head) and the last instruction (the tail) or end of the instruction stream contained in a basic block.  In fact, since the basic_block data type is used to represent blocks in both major intermediate representations of GCC (tree and RTL), there are pointers to the head and end of a basic block for both representations.

For RTL, these pointers are rtx head, end.  In the RTL function representation, the head pointer always points either to a NOTE_INSN_BASIC_BLOCK or to a CODE_LABEL, if present. In the RTL representation of a function, the instruction stream contains not only the ``real'' instructions, but also notes. Any function that moves or duplicates the basic blocks needs to take care of updating of these notes.  Many of these notes expect that the instruction stream consists of linear regions, making such updates difficult.   The 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 NOTE_INSN_BASIC_BLOCK,  but zero or more CODE_LABEL nodes can precede the block note.   A basic block ends by control flow instruction or last instruction before following CODE_LABEL or NOTE_INSN_BASIC_BLOCK.  A CODE_LABEL cannot appear in the instruction stream of a basic block.

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 fall-thru, the existence of such construct in the way needs to be checked by calling can_fallthru function.

For the tree representation, the head and end of the basic block are being pointed to by the stmt_list field, but this special 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 block statement iterators (BSIs).  Grep for ^bsi in the various tree-* files. The following snippet will pretty-print all the statements of the program in the GIMPLE representation.

     FOR_EACH_BB (bb)
       {
          block_stmt_iterator si;

          for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
            {
               tree stmt = bsi_stmt (si);
               print_generic_stmt (stderr, stmt, 0);
            }
       }

Edges
=====

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 edge data type.  Each edge acts as a link between two basic blocks: the src member of an edge points to the predecessor basic block of the dest basic block. The members preds and succs of the basic_block data type point to type-safe vectors of edges to the predecessors and successors of the block.

When walking the edges in an edge vector, edge iterators should be used.  Edge iterators are constructed using the edge_iterator data structure and several methods are available to operate on them:

ei_start
     This function initializes an edge_iterator that points to the first edge in a vector of edges.

ei_last
     This function initializes an edge_iterator that points to the last edge in a vector of edges.

ei_end_p
     This predicate is true if an edge_iterator represents the last edge in an edge vector.

ei_one_before_end_p
     This predicate is true if an edge_iterator represents the second last edge in an edge vector.

ei_next
     This function takes a pointer to an edge_iterator and makes it point to the next edge in the sequence.

ei_prev
     This function takes a pointer to an edge_iterator and makes it point to the previous edge in the sequence.

ei_edge
     This function returns the edge currently pointed to by an edge_iterator.

ei_safe_safe
     This function returns the edge currently pointed to by an edge_iterator, but returns 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 NULL edge indicates the end of the sequence.

The convenience macro 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:

     edge e;
     edge_iterator ei;

     FOR_EACH_EDGE (e, ei, bb->succs)
       {
          if (e->flags & EDGE_FALLTHRU)
            break;
       }

There are various reasons why control flow may transfer from one block to another.  One possibility is that some instruction, for example a CODE_LABEL, in a linearized instruction stream just always starts a new basic block.  In this case a 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 flags field of the 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:

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.

fall-thru
     Fall-thru edges are present in case where the basic block may continue execution to the following one without branching.  These edges have the 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 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.

exception handling
     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 EDGE_ABNORMAL and EDGE_EH flags set.

     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 purge_dead_edges call.

     In the RTL representation, the destination of an exception edge is specified by REG_EH_REGION note attached to the insn. In case of a trapping call the EDGE_ABNORMAL_CALL flag is set too.  In the tree representation, this extra flag is not set.

     In the RTL representation, the predicate may_trap_p may be used to check whether instruction still may trap or not.  For the tree representation, the tree_could_trap_p predicate is available, but this predicate only checks for possible memory traps, as in dereferencing an invalid pointer location.

sibling calls
     Sibling calls or tail calls terminate the function in a non-standard way and thus an edge to the exit must be present. EDGE_SIBCALL and EDGE_ABNORMAL are set in such case. These edges only exist in the RTL representation.

computed jumps
     Computed jumps contain edges to all labels in the function referenced from the code.  All those edges have 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 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,

            goto *x;
            [ ... ]

            goto *x;
            [ ... ]

            goto *x;
            [ ... ]

     factoring the computed jumps results in the following code sequence which has a much simpler flow graph:

            goto y;
            [ ... ]

            goto y;
            [ ... ]

            goto y;
            [ ... ]

          y:
            goto *x;

     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.

nonlocal goto handlers
     GCC allows nested functions to return into caller using a 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 EDGE_ABNORMAL and EDGE_ABNORMAL_CALL flags set.

function entry points
     By definition, execution of function starts at basic block 0, so there is always an edge from the ENTRY_BLOCK_PTR to basic block 0. There is no tree representation for alternate entry points at this moment.  In RTL, alternate entry points are specified by CODE_LABEL with 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.

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.

Profile information
===================

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 profile feedback, but it can also  estimate branch probabilities based on statics and heuristics.

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.

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 predict.def for details) and compute estimated frequencies of each basic block by propagating the probabilities over the graph.

Each basic_block contains two integer fields to represent profile information: frequency and count.  The 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 BB_FREQ_BASE.  The most frequently executed basic block in function is initially set to 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.

The 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 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.

Each edge also contains a branch probability field: an integer in the range from 0 to REG_BR_PROB_BASE.  It represents probability of passing control from the end of the src basic block to the dest basic block, i.e. the probability that control will flow along this edge.   The EDGE_FREQUENCY macro is available to compute how frequently a given edge is taken.  There is a 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 REG_BR_PROB macro) since they are used when instructions are output to the assembly file and the flow graph is no longer maintained.

The probability that control flow arrives via a given edge to its destination basic block is called reverse probability and is not directly represented, but it may be easily computed from frequencies of basic blocks.

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 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.

It is important to point out that REG_BR_PROB_BASE and 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 count field, as modern CPUs are fast enough to execute $2^32$ operations quickly.

Maintaining the CFG
===================

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 basic_block and 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 hooks is defined so that each representation can provide its own implementation of CFG manipulation routines when necessary.  These hooks are defined in 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 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 tree representation is not an integral part of the representation, in that a function tree may be expanded without first building a  flow graph for the tree representation at all.  This happens when compiling without any tree optimization enabled.  When the 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 tree representation can not be easily used or maintained without proper maintenance of the CFG simultaneously.

In the RTL representation, each instruction has a BLOCK_FOR_INSN value that represents pointer to the basic block that contains the instruction.  In the tree representation, the function bb_for_stmt returns a pointer to the basic block containing the queried statement.

When changes need to be applied to a function in its tree representation, block statement iterators should be used.  These iterators provide an integrated abstraction of the flow graph and the instruction stream.  Block statement iterators are constructed using the block_stmt_iterator data structure and several modifier are available, including the following:

bsi_start
     This function initializes a block_stmt_iterator that points to the first non-empty statement in a basic block.

bsi_last
     This function initializes a block_stmt_iterator that points to the last statement in a basic block.

bsi_end_p
     This predicate is true if a block_stmt_iterator represents the end of a basic block.

bsi_next
     This function takes a block_stmt_iterator and makes it point to its successor.

bsi_prev
     This function takes a block_stmt_iterator and makes it point to its predecessor.

bsi_insert_after
     This function inserts a statement after the 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.

bsi_insert_before
     This function inserts a statement before the 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.

bsi_remove
     This function removes the block_stmt_iterator passed in and rechains the remaining statements in a basic block, if any.

In the RTL representation, the macros BB_HEAD and BB_END may be used to get the head and end rtx of a basic block.  No abstract iterators are defined for traversing the insn chain, but you can just use NEXT_INSN and PREV_INSN instead.  See Insns.

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 purge_dead_edges on a given basic block to remove superfluous edges, if any.

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 redirect_edge_and_branch is preferred over more low level functions, such as redirect_jump that operate on RTL chain only.  The CFG hooks defined in cfghooks.h should provide the complete API required for manipulating and maintaining the CFG.

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 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.

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 insert_insn_on_edge function that emits an instruction ``on the edge'', caching it for a later 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 tree representation, the equivalent functions are bsi_insert_on_edge which inserts a block statement iterator on an edge, and bsi_commit_edge_inserts which flushes the instruction to actual instruction stream.

While debugging the optimization pass, an 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 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 tree itself.

Liveness information
====================

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 pass_df_initialize and ending with pass_df_finish.  Three flavors of live analysis are available: With LR, it is possible to determine at any point P in the function if the register may be used on some path from P to the end of the function.  With UR, it is possible to determine if there is a path from the beginning of the function to P that defines the variable. LIVE is the intersection of the LR and UR and a variable is live at P if there is both an assignment that reaches it from the beginning of the function and a uses that can be reached on some path from P to the end of the function.

In general LIVE is the most useful of the three.  The macros 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 df_analyze.  See the file df-core.c for details on using the dataflow.

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 REG_DEAD notes representing that the value of a given register is no longer needed, or 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.