GNU Compiler Collection (GCC) 4.2 Internals

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