Control Flow Graph Factory Terminology

Control flow graphs generated by Control Flow Graph Factory are directed graphs or digraphs.

Digraph can be defined as an ordered pair G : = (V, A), where V is a set of elements called vertices or nodes, and A is a set of ordered pairs of vertices, called arcs, directed edges, or arrows.

A Control Flow Graph (CFG) in computer science is a diagrammatic representation of a program code. The code may be source code, assembly code, java bytecode or some other sequence of instructions. The instructions or sourcecode lines are represented as vertices and the possible program execution paths are arcs.

Control Flow Graph Factory offers the following control flow graph options:

Bytecode Graph

The vertices in this graph are Java bytecode instructions and arcs are the possible control transitions beetween these instructions.

public static void test3(int i) {
    0 iload_0;      /* i */
    1 ifne 9;
    4 iinc 0 1;     /* i++ */
    7 goto 6;
    10 iinc 0 -1;   /* i-- */
    13 return;
}
Example Bytecode Graph

Back to the top

Source Code Graph

The vertices in this graph are source code lines and arcs are the possible control transitions beetween these instructions.

Note: Control Flow Graph Factory generates Source Code Graph from the bytecode of the corresponding method using Line Number Table.

Important consequences of this are

  • It is not possible to generate Source Code Graphs for .java files which are not included in the build path of some Java project in Eclipse.
  • The source code graph can be only generated for classes which have LineNumberTable Attribute compiled-in.
public static void test3(int i) {
    0 iload_0;        /* i */
    1 ifne 9;
    4 iinc 0 1;       /* i++ */
    7 goto 6;
    10 iinc 0 -1;     /* i-- */
    13 return;
    
    /*    LineNumberTable     */
    /* ---------+-------------*/
    /* start_pc | line_number */
    /* ---------+-------------*/
    /*        0 +          75 */
    /*        4 +          76 */
    /*       10 +          79 */
    /*       13 +          81 */
    /* ---------+-------------*/
}
Example Sourcecode Graph

Back to the top

Basic Block Graph

Vertices in Basic Block Graphs are basic blocks.

Basic block is a sequence of instructions where (i) the instruction on each position always executes before all instructions on later positions and (ii) no other instruction executes between two instructions in the sequence.

Basic blocks are usually the units to which compiler optimizations are applied.

Control Flow Graph Factory generates Basic Block Graphs through transformation from Bytecode Graphs using DFS algorithm.

public static void test3(int i) {
  B1 {
    0 iload_0;     /* i */
    1 ifne 9;
  }

  B4 {
    4 iinc 0 1;   /* i++ */
    7 goto 6;
  }

  B2 {  
    10 iinc 0 -1; /* i-- */
  }
  
  B3 {
    13 return;
  }
}
Basic block graph example

Back to the top

Virtual Elements

Control Flow Graph Factory can be set up to generate the following virtual elements:

  • Start Node - the node through which control flow enters the graph
  • Exit Node - the node through which control flow leaves the graph
  • Back Edge - an directed edge from exit node to the start node.
  • Comments - the Line Number Table can be generated as a comment element.
Graph example with virtual elements

Back to the top