# CS606 - Compiler Construction - Lecture Handout 43

User Rating:  / 0
PoorBest

## Control Flow Graph - CFG

A control flow graph is the triplet CFG = < V, E, Entry >, where V = vertices or nodes, representing an instruction or basic block (group of statements), E = (V x V) edges, potential flow of control. Entry is an element of V, the unique program entry.

## Basic Blocks

A basic block is a sequence of consecutive statements with single entry/single exit. Flow of control only enters at the beginning and only leaves at the end. The can be variants of basic blocks with single entry/multiple exit, multiple entry/single exit.

## Generating CFGs

In order to generate a CFG, we partition the intermediate code (3-address code, for example) into basic blocks. Edges are added corresponding to control flow between blocks. An unconditional goto in the IR will lead to a single edge to another or the same block. A conditional goto will lead to multiple edges. If there is no goto at the end of a
block, the control passes to first statement of next block.

Here is the algorithm for partitioning intermediate code into basic blocks. The input to the algorithm is a sequence of three-address statements. The algorithm will output a list of basic blocks with each three-address statements in exactly one block.

Algorithm: partition 3-address statements into basic blocks:

1. Determine the set of leaders – the first statements of basic blocks. The rules are:
• The first statement is a leader
• Any statement that is the target of a conditional or unconditional goto is a leader
• Any statement that immediately follows a goto or conditional goto is a leader
2. For each leader, its basic block consists of the leader and all statements up to but not including the next leader or the end of the program

Example: consider the C fragment for computing dot product aT b of two vectors a and b of length 20

The two basic blocks are

This yields the following CFG; note that the target of the condition goto at the end of the second block has been replaced by reference to block 2.

Let us consider a more complex example. Here is the quicksort algorithm encoded as a recursive function in C++

i = 1
Quick Sort
void quicksort(int m, int n)
{
int i,j,v,x;
if( n <= m ) return;
i=m-1; j=n; v=a[n];
while(true) {
do i=i+1; while( a[i] < v);
do j=j-1; while( a[j] > v);
i( i >= j ) break;
x=a[i]; a[i]=a[j]; a[j]=x;
}
x=a[i]; a[i]=a[n]; a[n]=x;
quicksort(m,j); quicksort(i+1,n);
}

The 3-address for the highlighted portion of the routine (the recursive calls have been left out) with the leaders highlighted and the resulting CFG is

## Basic Block Code Generation

The code generation can carried out at the basic block level. A number of strategies are available to generate code from a basic block. The three we will discuss are

1. Basic - using liveness information
2. Using DAGS - node numbering
3. Register Allocation

In case of the basic code generation strategy, the generator deals with each basic block individually to emit machine code for the block using liveness information. At the end of the block, the generator emits code to save any live values left in registers.

## Computing Live/Next Use Information

For the statement:

x = y + z

x has a next use if there is a statement s that references x and there is some way for control to flow from the original statement to s.

x = y + z
......
......
s t1 = x – t3

A variable is live at a given point in time if it has a next use. Liveness tells us whether we care about the value held by a variable. Here is the algorithm for computing live status of variables in a basic block”

Algorithm: Computing live status
Input:
A basic block.
Output:
For each statement, set of live variables

Method:

1. Initially all non-temporary variables go into live set.
2. for i = last statement to first statement:
for statement i: x = y op z
attach to statement i, current live set.
remove x from set.
add y and z to set.