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
