Edges

Edges in the control flow graphs are described by structure:

/* Control flow edge information.  */
typedef struct edge_def {
  /* Links through the predecessor and successor lists.  */
  struct edge_def *pred_next, *succ_next;

  /* The two blocks at the ends of the edge.  */
  struct basic_block_def *src, *dest;

  /* Instructions queued on the edge.  */
  rtx insns;

  /* Auxiliary info specific to a pass.  */
  void *aux;

  int flags;			/* see EDGE_* below  */
  int probability;		/* biased by REG_BR_PROB_BASE */
  gcov_type count;		/* Expected number of executions calculated
				   in profile.c  */
} *edge;

Edges represent possible control flow transfers from the end of basic block to the head of another. Single linked lists of edges to predecessors and successors are maintained for each basic block.

In common case edges correspond to branches or ``fall-thru'' edges to the following basic block, but there are several other reasons why edge may be created. The type of edge can be obtained via flags field.

There are following types:

jumps

Edges corresponding to destinations of jump instructions have no flags defined. These edges are used for unconditional or conditional jumps and table jumps and are most convenient to manipulate with as they may be freely redirected.

fall-thru

Fall-thru edges are present in case the basic block may continue execution to the following one without branching and do have EDGE_FALLTHRU flag set.

Unlike other types of edges, these edges must come into following basic block in the insn stream and thus function force_nonfallthru is available to insert jump in the case that redirection is needed. This may require creation of a new basic block.

exception handling

Exception handling edges represent possible control
transfers from trap to the exception handler. The definition of trap 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.

The destination of edge is specified by REG_EH_REGION note attached to the insn.

The flags of such notes set EDGE_EH and EDGE_ABNORMAL. In case of the call EDGE_ABNORMAL_CALL flag is set too.

When updating the insn stream it is easy to change possibly trapping instruction to non-trapping. Opposite conversion is difficult and should not happen. Predicate may_trap_p may be used to check whether instruction still may trap or not. The edges can be eliminated via purge_dead_edges call.

sibling calls

Sibling calls terminate the function in a non-standard way and thus an edge to the exit must be present. EDGE_ABNORMAL_CALL and EDGE_ABNORMAL are set in such case.

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.

nonlocal goto handlers

GCC allows nested functions to return into caller using goto statement referring to label passed to as an argument. The labels passed to nested functions contain special code to cleanup after function call. Such section of code is referred as nonlocal goto receivers. In the case function contains such nonlocal goto receivers, the edge from the call to label is present having EDGE_ABNORMAL and EDGE_ABNORMAL_CALL flags set.

function entry points

By definition, execution of function starts by basic block 0, so there is always an edge from entry block to the first real basic block. The 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. In future full support for multiple entry functions defined by Fortran 90 needs to be implemented.

function exits

In the pre-reload representation function terminates by 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.