Next:Profile information, Previous:Basic Blocks, Up:Control Flow Graph [Contents][Index]
Edges represent possible control flow transfers from the end of somebasic block A to the head of another basic block B. We say that A isa predecessor of B, and B is a successor of A. Edges are representedin GCC with theedge data type. Eachedge acts as alink between two basic blocks: Thesrc member of an edgepoints to the predecessor basic block of thedest basic block.The memberspreds andsuccs of thebasic_block datatype point to type-safe vectors of edges to the predecessors andsuccessors of the block.
When walking the edges in an edge vector,edge iterators shouldbe used. Edge iterators are constructed using theedge_iterator data structure and several methods are availableto operate on them:
ei_start ¶This function initializes anedge_iterator that points to thefirst edge in a vector of edges.
ei_last ¶This function initializes anedge_iterator that points to thelast edge in a vector of edges.
ei_end_p ¶This predicate istrue if anedge_iterator representsthe last edge in an edge vector.
ei_one_before_end_p ¶This predicate istrue if anedge_iterator representsthe second last edge in an edge vector.
ei_next ¶This function takes a pointer to anedge_iterator and makes itpoint to the next edge in the sequence.
ei_prev ¶This function takes a pointer to anedge_iterator and makes itpoint to the previous edge in the sequence.
ei_edge ¶This function returns theedge currently pointed to by anedge_iterator.
ei_safe_edge ¶This function returns theedge currently pointed to by anedge_iterator, but returnsNULL if the iterator ispointing at the end of the sequence. This function has been providedfor existing code makes the assumption that aNULL edgeindicates the end of the sequence.
The convenience macroFOR_EACH_EDGE can be used to visit all ofthe edges in a sequence of predecessor or successor edges. It mustnot be used when an element might be removed during the traversal,otherwise elements will be missed. Here is an example of how to usethe 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 blockto another. One possibility is that some instruction, for example aCODE_LABEL, in a linearized instruction stream just alwaysstarts a new basic block. In this case afall-thru edge linksthe basic block to the first following basic block. But there areseveral other reasons why edges may be created. Theflagsfield of theedge data type is used to store informationabout the type of edge we are dealing with. Each edge is of one ofthe following types:
No type flags are set for edges corresponding to jump instructions.These edges are used for unconditional or conditional jumps and inRTL also for table jumps. They are the easiest to manipulate as theymay be freely redirected when the flow graph is not in SSA form.
Fall-thru edges are present in case where the basic block may continueexecution to the following one without branching. These edges havetheEDGE_FALLTHRU flag set. Unlike other types of edges, theseedges must come into the basic block immediately following in theinstruction stream. The functionforce_nonfallthru isavailable to insert an unconditional jump in the case that redirectionis needed. Note that this may require creation of a new basic block.
Exception handling edges represent possible control transfers from atrapping instruction to an exception handler. The definition of“trapping” varies. In C++, only function calls can throw, but forAda exceptions like division by zero or segmentation fault aredefined and thus each instruction possibly throwing this kind ofexception needs to be handled as control flow instruction. Exceptionedges have theEDGE_ABNORMAL andEDGE_EH flags set.
When updating the instruction stream it is easy to change possiblytrapping instruction to non-trapping, by simply removing the exceptionedge. The opposite conversion is difficult, but should not happenanyway. The edges can be eliminated viapurge_dead_edges call.
In the RTL representation, aREG_EH_REGION note is attached toan instruction that can throw an exception. The destination of theexception edge originating at such an instruction is specified by thevalue of theREG_EH_REGION note. In case of a trapping calltheEDGE_ABNORMAL_CALL flag is set too. In theGIMPLErepresentation, this extra flag is not set.
In the RTL representation, the predicatemay_trap_p may be usedto check whether instruction still may trap or not. For the treerepresentation, thetree_could_trap_p predicate is available,but this predicate only checks for possible memory traps, as indereferencing an invalid pointer location.
Sibling calls or tail calls terminate the function in a non-standardway and thus an edge to the exit must be present.EDGE_SIBCALL andEDGE_ABNORMAL are set in such case.These edges only exist in the RTL representation.
Computed jumps contain edges to all labels in the function referencedfrom the code. All those edges haveEDGE_ABNORMAL flag set.The edges used to represent computed jumps often cause compile timeperformance problems, since functions consisting of many taken labelsand many computed jumps may havevery dense flow graphs, sothese edges need to be handled with special care. During the earlierstages of the compilation process, GCC tries to avoid such dense flowgraphs by factoring computed jumps. For example, given the followingseries of jumps,
goto *x; [ … ] goto *x; [ … ] goto *x; [ … ]
factoring the computed jumps results in the following code sequencewhich 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 aruntime cost in there resulting code: An extra jump. Therefore, thecomputed jumps are un-factored in the later passes of the compiler(in the pass calledpass_duplicate_computed_gotos).Be aware of that when you work on passes in that area. There havebeen numerous examples already where the compile time for code withunfactored computed jumps caused some serious headaches.
GCC allows nested functions to return into caller using agototo a label passed to as an argument to the callee. The labels passedto nested functions contain special code to cleanup after functioncall. Such sections of code are referred to as “nonlocal gotoreceivers”. If a function contains such nonlocal goto receivers, anedge from the call to the label is created with theEDGE_ABNORMAL andEDGE_ABNORMAL_CALL flags set.
By definition, execution of function starts at basic block 0, so thereis always an edge from theENTRY_BLOCK_PTR to basic block 0.There is noGIMPLE representation for alternate entry points atthis moment. In RTL, alternate entry points are specified byCODE_LABEL withLABEL_ALTERNATE_NAME defined. Thisfeature is currently used for multiple entry point prologues and islimited to post-reload passes only. This can be used by back-ends toemit alternate prologues for functions called from different contexts.In future full support for multiple entry functions defined by Fortran90 needs to be implemented.
In the pre-reload representation a function terminates after the lastinstruction in the insn chain and no explicit return instructions areused. This corresponds to the fall-thru edge into exit block. Afterreload, optimal RTL epilogues are used that use explicit (conditional)return instructions that are represented by edges with no flags set.
Next:Profile information, Previous:Basic Blocks, Up:Control Flow Graph [Contents][Index]