Basic Block

Basic block contains a sequence of statement. The flow of control enters at the beginning of the statement and leave at the end without any halt (except may be the last instruction of the block).

The following sequence of three address statements forms a basic block:

t1:= x * x
t2:= x * y
t3:= 2 * t2
t4:= t1 + t3
t5:= y * y
t6:= t4 + t5

Basic block construction:

Algorithm: Partition into basic blocks

Input: It contains the sequence of three address statements

Output: it contains a list of basic blocks with each three address statement in exactly one block

Method: First identify the leader in the code. The rules for finding leaders are as follows:

• The first statement is a leader.
• Statement L is a leader if there is an conditional or unconditional goto statement like: if....goto L or goto L
• Instruction L is a leader if it immediately follows a goto or conditional goto statement like: if goto B or goto B

For each leader, its basic block consists of the leader and all statement up to. It doesn't include the next leader or end of the program.

Consider the following source code for dot product of two vectors a and b of length 10:

begin 
           prod :=0; 
i:=1; 
do begin 
prod :=prod+ a[i] * b[i]; 
i :=i+1; 
end 
while i <= 10 
end

The three address code for the above source program is given below:

B1

(1)	prod := 0 
(2)	i := 1

B2

(3)	t1 := 4* i 
(4)	t2 := a[t1] 
(5)	t3 := 4* i 
(6)	t4 := b[t3] 
(7)	t5 := t2*t4 
(8)	t6 := prod+t5 
(9)	prod := t6 
(10)	t7 := i+1 
(11)	i := t7 
(12)	if i<=10 goto (3)	

Basic block B1 contains the statement (1) to (2)

Basic block B2 contains the statement (3) to (12)