Basic Blocks in Compiler Design
Again freestudy9 comes with a new post related to basic Blocks.
- A basic block is a sequence of consecutive statements in which flow of control enters at the beginning and leaves at the end without halt or possibility of branching except at the end.
- The following sequence of three address statements forms a basic block:three-address
t1 := a*a
t2 := a*b
t3 := 2*t2
t4 := t1+t3
t5 := b*b t6 := t4+t5
- Some terminology used in basic blocks are given below:
- A three-address statement x address x:=y+z is said to define x and to use y or z. A name in a basic block is said to be live at a given point if its value is used after that point in the program, perhaps in another basic block.
- The following algorithm can be used to partition a sequence of three-address statements into basic blocks.
Algorithm: Partition into basic blocks
Input: A sequence of the three-address statements.
Output: A list of basic blocks with each three address statement in exactly one block.three-address
We first determine the set of leaders, for that we use the following rules:
i) The first statement is a leader.
ii) Any statement that is the target of a conditional or unconditional goto is a leader.
iii) Any statement that immediately follows a goto or conditional goto statement is a leader.
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: Program to compute dot product
prod := 0;
i := 1;
prod := prod + a[t1] * b[t2];
i := i+1;
while i<= 20
Three address code for the above program,
(1) prod := 0
(2) i := 1
(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<=20 goto (3)
Algorithm for three-address
Let us apply an algorithm to the three address code to determine its basic blocks.
- Statement (1) is a leader by rule (I) and statement (3) is a leader by rule (II) since the last statement can jump to it.
- Therefore, statements (1) and (2) form a basic block.
- The remainder of the program beginning with a statement (3) forms a second basic block.