Basic Blocks:
Basic blocks are very useful while performing code optimization transformations, and also in code generations
What is Basic block?
Basic block is a sequence of consecutive statements which may be entered only at the beginning, and when entered, they are executed in the sequence without halt or possibility of a branch
An example of the basic block is shown below
t1 := a*5
t2 := t1+7
t3:= t2-5
t4 := t1 + t3
t5 := t2 + b
Algorithm for partitioning a sequence of Three Address Statements into Basic Blocks
First determine the leaders, that is, the first statements of basic blocks. The rules used to locate leaders are:
The first statement is a leader
Any statement which is the target of a conditional or unconditional goto is a leader
Any statement which immediately follows a conditional goto is a leader
For each leader construct its basic block, which consists of the leader and all statements up to but not including the next leader or the end of the program. Any statement not placed in a block can never be executed and may now be removed, if desired”
Flow Graphs:
Flow graphs are used to depict the basic blocks, and their successor relationships by a directed graph
Drawing the flow graph
In a flow graph, one node is distinguished as the initial; it is the basic block whose leader is the first statement. There is a directed edge from block B1 to block B2 could immediately follow B1 during execution, that is if:
§ There is a conditional or unconditional jump from the last statement or B1 to the first statement of B2 or
§ B2 immediately follows B1 in the order of the program, and B1 does not end in an unconditional jump
§ It is said, that B1 is a predecessor of B2, and B2 is a successor of B1
Example:
Basic blocks
· Consider the following pascal code to compute the product of two one dimensional arrays a and b of length 20 and its three address code as shown below
begin
(1) Prod : =0
(2) i := 1
(3) t1 := 4 * i
(4) t2 := addr(a) – 4
(5) t3 := t2[t1]
(6) t4 := addr(b) – 4
(7) t5 := t4[t1]
(8) t6 := t3 * t5
(9) PROD := PROD +t6
(10)i := i + 1
(11)if I ≤2 0 goto (3)
Now, The basic block for the TAC are:
Figure 29
As per the algorithm statement (1), (3) and following statement (11) are leaders
So, basic blocks B1 contains statement (1) to (2) and (3) is a leader. B2 contains statements from (3) to (11)
The flow graph for the previous basic blocks is:
Figure 30
Common Subexpression Elimination
An expression E as common subexpression, if E was previously computed and the value of variables in E have not changed since the previous computation
If common subexpressions can be locate, one can avoid recomputing the expression by using the previously compute value
Consider the C code snippet and its TAC:
a = b + c + d
a1 = b + c + e
(1) t1 = b + c
(2) t2 = t1 + d
(3) a = t2
(4) t3 = b + c
(5) t4 = t3 + e
(6) a1 = t4
Here, the expression b + c is computed twice at statements (1) and (4) without changes in the value of band c. So, these common subexpressions can be eliminated. And by eliminating these common subexpressions t3 and t4 can also be eliminated. Now the TAC becomes:
(1) t1 = b + c
(2) t2 = t1 + d
(3) a = t2
(4) t4 = t2 + e
(5) a1 = t4
Copy Propagation
A statement of the form a = b is called as copy statement. The idea behind copy propagation transformation is to use b in place of a whenever possible after the copy statement a = b
Consider the following TAC
(1) t1 = 0
(2) t2 = &arr
(3) t2[t1] = 44
(4) t3 = 4
(5) t4 = &arr
(6) t4[t3] = 55
It has two copy statements (1) and (4)
Now, after applying copy propagation transformation, i.e., replacing t1 by 0 after statement (1) and t3 by statement (4), the TAC becomes:
(1) t1 = 0
(2) t2 = &arr
(3) t2[0] = 44
(4) t3 = 4
(5) t4 = &arr
(6) t4[4] = 55
0 comments:
Post a Comment