Control Flow Graphs

Control Flow Graphs:

A control-flow graph (CFG) is a representation, using graph notation, of all paths that might be traversed through a program during its execution. The control-flow graph is due to Frances E. Allen, who notes that Reese T. Prosser used boolean connectivity matrices for flow analysis before.

In a control-flow graph each node in the graph represents a basic block, i.e. a straight-line piece of code without any jumps or jump targets; jump targets start a block, and jumps end a block. Directed edges are used to represent jumps in the control flow.

Steps:

Number all the statements of a program.

Numbered statements represent nodes of the control flow graph.

An edge from one node to another node exists:

if execution of the statement representing the first node can result in transfer of control to the other node. 

Sequence: 

1. a=5;
2. b=a*b-1

Selection:

1. if(a>b) then
2. c=3;
3. Else
4. c=5;
5. c=c*c;

Iteration:

1. while(a>b){
2. b=b*a;
3. b=b-1;
4. }
5. c=b+d;

Path:

• A path through a program:
  • a node and edge sequence from the starting node to a terminal node of the control flow graph.
• There may be several terminal nodes for the program.
• Any path through the program: 
• introducing at least one new node that is not included in any other independent paths.
• Provides a practical way of determining the maximum number of linearly independent paths in a program.