BASIC BLOCKS AND FLOW GRAPHS
t2 : = a * b
t3 : = 2 * t2
t4 : = t1 + t3
t5 : = b * b
t6 : = t4 + t5
Basic Block Construction:
Algorithm: Partition into basic blocks
Input: A sequence of three-address statements
Output: A list of basic blocks with each three-address statement in exactly one block Method:
1. We first determine the set of leaders, the first statements of basic blocks. The rules we use are of the following:
a. The first statement is a leader.
b. Any statement that is the target of a conditional or unconditional goto is a leader.
c. Any statement that immediately follows a goto or conditional goto statementis 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.
Consider the following source code for dot product of two vectors:
The three-address code for the above source program is given as :
(1) prod := 0
(2) i := 1
(3) t1 := 4* i
(4) t2 := a[t1] /*compute a[i] */
(5) t3 := 4* i
(6) t4 := b[t3] /*compute b[i] */
(7) t5 := t2*t4
(8) t6 := prod+t5
(9) prod := t6
(10) t7 := i+1
(11) i := t7
(12) if i<=20 goto (3)
Basic block 1: Statement (1) to (2)
Basic block 2: Statement (3) to (12)
Transformations on Basic Blocks:
A number of transformations can be applied to a basic block without expressions computed by the block. Two important classes of transformation are :
1. Structure preserving transformations:
a) Common subexpression elimination:
a : = b + c - - > a : = b + c
b : = a - d - - > b : = a - d
c : = b + c - - > c : = b + c
d : = a - d - - > d : = b
Since the second and fourth expressions compute the same expression, the basic block can be transformed as above.
b) Dead-code elimination:
Suppose x is dead, that is, never subsequently used, at the point where the statement x : = y + z appears in a basic block. Then this statement may be safely removed without changing the value of the basic block.
c) Renaming temporary variables:
A statement t : = b + c ( t is a temporary ) can be changed to u : = b + c (u is a new temporary) and all uses of this instance of t can be changed to u without changing the value of the basic block. Such a block is called a normal-form block.
d) Interchange of statements:
Suppose a block has the following two adjacent statements:
t1 : = b + c
t2 : = x + y
We can interchange the two statements without affecting the value of the block if and only if neither x nor y is t1 and neither b nor c is t2.
2. Algebraic transformations:
Algebraic transformations can be used to change the set of expressions computed by a basic block into an algebraically equivalent set.
i) x : = x + 0 or x : = x * 1 can be eliminated from a basic block without changing the set of expressions it computes.
ii) The exponential statement x : = y * * 2 can be replaced by x : = y * y.
The nodes of the flow graph are basic blocks. It has a distinguished initial node.
Fig. 4.2 Flow graph for program
1. All nodes in the collection are strongly connected.
2. The collection of nodes has a unique entry.