gccint: Edges
1
1 15.2 Edges
1 ==========
1
1 Edges represent possible control flow transfers from the end of some
1 basic block A to the head of another basic block B. We say that A is a
1 predecessor of B, and B is a successor of A. Edges are represented in
1 GCC with the 'edge' data type. Each 'edge' acts as a link between two
1 basic blocks: The 'src' member of an edge points to the predecessor
1 basic block of the 'dest' basic block. The members 'preds' and 'succs'
1 of the 'basic_block' data type point to type-safe vectors of edges to
1 the predecessors and successors of the block.
1
1 When walking the edges in an edge vector, "edge iterators" should be
1 used. Edge iterators are constructed using the 'edge_iterator' data
1 structure and several methods are available to operate on them:
1
1 'ei_start'
1 This function initializes an 'edge_iterator' that points to the
1 first edge in a vector of edges.
1
1 'ei_last'
1 This function initializes an 'edge_iterator' that points to the
1 last edge in a vector of edges.
1
1 'ei_end_p'
1 This predicate is 'true' if an 'edge_iterator' represents the last
1 edge in an edge vector.
1
1 'ei_one_before_end_p'
1 This predicate is 'true' if an 'edge_iterator' represents the
1 second last edge in an edge vector.
1
1 'ei_next'
1 This function takes a pointer to an 'edge_iterator' and makes it
1 point to the next edge in the sequence.
1
1 'ei_prev'
1 This function takes a pointer to an 'edge_iterator' and makes it
1 point to the previous edge in the sequence.
1
1 'ei_edge'
1 This function returns the 'edge' currently pointed to by an
1 'edge_iterator'.
1
1 'ei_safe_safe'
1 This function returns the 'edge' currently pointed to by an
1 'edge_iterator', but returns 'NULL' if the iterator is pointing at
1 the end of the sequence. This function has been provided for
1 existing code makes the assumption that a 'NULL' edge indicates the
1 end of the sequence.
1
1 The convenience macro 'FOR_EACH_EDGE' can be used to visit all of the
1 edges in a sequence of predecessor or successor edges. It must not be
1 used when an element might be removed during the traversal, otherwise
1 elements will be missed. Here is an example of how to use the macro:
1
1 edge e;
1 edge_iterator ei;
1
1 FOR_EACH_EDGE (e, ei, bb->succs)
1 {
1 if (e->flags & EDGE_FALLTHRU)
1 break;
1 }
1
1 There are various reasons why control flow may transfer from one block
1 to another. One possibility is that some instruction, for example a
1 'CODE_LABEL', in a linearized instruction stream just always starts a
1 new basic block. In this case a "fall-thru" edge links the basic block
1 to the first following basic block. But there are several other reasons
1 why edges may be created. The 'flags' field of the 'edge' data type is
1 used to store information about the type of edge we are dealing with.
1 Each edge is of one of the following types:
1
1 _jump_
1 No type flags are set for edges corresponding to jump instructions.
1 These edges are used for unconditional or conditional jumps and in
1 RTL also for table jumps. They are the easiest to manipulate as
1 they may be freely redirected when the flow graph is not in SSA
1 form.
1
1 _fall-thru_
1 Fall-thru edges are present in case where the basic block may
1 continue execution to the following one without branching. These
1 edges have the 'EDGE_FALLTHRU' flag set. Unlike other types of
1 edges, these edges must come into the basic block immediately
1 following in the instruction stream. The function
1 'force_nonfallthru' is available to insert an unconditional jump in
1 the case that redirection is needed. Note that this may require
1 creation of a new basic block.
1
1 _exception handling_
1 Exception handling edges represent possible control transfers from
1 a trapping instruction to an exception handler. The definition of
1 "trapping" varies. In C++, only function calls can throw, but for
1 Ada exceptions like division by zero or segmentation fault are
1 defined and thus each instruction possibly throwing this kind of
1 exception needs to be handled as control flow instruction.
1 Exception edges have the 'EDGE_ABNORMAL' and 'EDGE_EH' flags set.
1
1 When updating the instruction stream it is easy to change possibly
1 trapping instruction to non-trapping, by simply removing the
1 exception edge. The opposite conversion is difficult, but should
1 not happen anyway. The edges can be eliminated via
1 'purge_dead_edges' call.
1
1 In the RTL representation, the destination of an exception edge is
1 specified by 'REG_EH_REGION' note attached to the insn. In case of
1 a trapping call the 'EDGE_ABNORMAL_CALL' flag is set too. In the
1 'GIMPLE' representation, this extra flag is not set.
1
1 In the RTL representation, the predicate 'may_trap_p' may be used
1 to check whether instruction still may trap or not. For the tree
1 representation, the 'tree_could_trap_p' predicate is available, but
1 this predicate only checks for possible memory traps, as in
1 dereferencing an invalid pointer location.
1
1 _sibling calls_
1 Sibling calls or tail calls terminate the function in a
1 non-standard way and thus an edge to the exit must be present.
1 'EDGE_SIBCALL' and 'EDGE_ABNORMAL' are set in such case. These
1 edges only exist in the RTL representation.
1
1 _computed jumps_
1 Computed jumps contain edges to all labels in the function
1 referenced from the code. All those edges have 'EDGE_ABNORMAL'
1 flag set. The edges used to represent computed jumps often cause
1 compile time performance problems, since functions consisting of
1 many taken labels and many computed jumps may have _very_ dense
1 flow graphs, so these edges need to be handled with special care.
1 During the earlier stages of the compilation process, GCC tries to
1 avoid such dense flow graphs by factoring computed jumps. For
1 example, given the following series of jumps,
1
1 goto *x;
1 [ ... ]
1
1 goto *x;
1 [ ... ]
1
1 goto *x;
1 [ ... ]
1
1 factoring the computed jumps results in the following code sequence
1 which has a much simpler flow graph:
1
1 goto y;
1 [ ... ]
1
1 goto y;
1 [ ... ]
1
1 goto y;
1 [ ... ]
1
1 y:
1 goto *x;
1
1 However, the classic problem with this transformation is that it
1 has a runtime cost in there resulting code: An extra jump.
1 Therefore, the computed jumps are un-factored in the later passes
1 of the compiler (in the pass called
1 'pass_duplicate_computed_gotos'). Be aware of that when you work
1 on passes in that area. There have been numerous examples already
1 where the compile time for code with unfactored computed jumps
1 caused some serious headaches.
1
1 _nonlocal goto handlers_
1 GCC allows nested functions to return into caller using a 'goto' to
1 a label passed to as an argument to the callee. The labels passed
1 to nested functions contain special code to cleanup after function
1 call. Such sections of code are referred to as "nonlocal goto
1 receivers". If a function contains such nonlocal goto receivers,
1 an edge from the call to the label is created with the
1 'EDGE_ABNORMAL' and 'EDGE_ABNORMAL_CALL' flags set.
1
1 _function entry points_
1 By definition, execution of function starts at basic block 0, so
1 there is always an edge from the 'ENTRY_BLOCK_PTR' to basic block
1 0. There is no 'GIMPLE' representation for alternate entry points
1 at this moment. In RTL, alternate entry points are specified by
1 'CODE_LABEL' with 'LABEL_ALTERNATE_NAME' defined. This feature is
1 currently used for multiple entry point prologues and is limited to
1 post-reload passes only. This can be used by back-ends to emit
1 alternate prologues for functions called from different contexts.
1 In future full support for multiple entry functions defined by
1 Fortran 90 needs to be implemented.
1
1 _function exits_
1 In the pre-reload representation a function terminates after the
1 last instruction in the insn chain and no explicit return
1 instructions are used. This corresponds to the fall-thru edge into
1 exit block. After reload, optimal RTL epilogues are used that use
1 explicit (conditional) return instructions that are represented by
1 edges with no flags set.
1