CD UNIT V Basic Blocks

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 any halt or possibility of branching except at the end.
 The following sequence of three-address statements forms a basic block:
t1 : = a * a
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 statement
is 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 a and b of length 20
begin
prod :=0;
i:=1;
do begin
prod :=prod+ a[i] * b[i];
i :=i+1;
end
while i <= 20
end
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 changing the set of
expressions computed by the block. Two important classes of transformation are :
 Structure-preserving transformations
 Algebraic transformations
1. Structure preserving transformations:

a) Common subexpression elimination:
a:=b+ca:=b+c
b:=a–db:=a-d
c:=b+cc:=b+c
d:=a–dd:=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
basicblock into an algebraically equivalent set.
Examples:
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.
Flow Graphs
 Flow graph is a directed graph containing the flow-of-control information for the set of
basic blocks making up a program.
 The nodes of the flow graph are basic blocks. It has a distinguished.
E.g.: Flow graph for the vector dot product is given as follows:
prod : = 0 Basic Block B1

i:=1
t1 : = 4 * i
t2 : = a [ t1 ]
t3 : = 4 * i
Basic Block B2
t4 : = b [ t3 ]
t5 : = t2 * t4
t6 : = prod + t5
prod : = t6
t7 : = i + 1
i : = t7
if i <= 20 goto B2
Flow Graph
B1 is the initial node. B2 immediately follows B1, so there is an edge from B1 to B2. The
target of jump from last statement of B1 is the first statement B2, so there is an edge fromB1 (last
statement) to B2 (first statement).
 B1 is the predecessor of B2, and B2 is a successor of B1.
Loops
 A loop is a collection of nodes in a flow graph such that
All nodes in the collection are strongly connected.
The collection of nodes has a unique entry.
 A loop that contains no other loops is called an inner loop.
NEXT-USE INFORMATION
 If the name in a register is no longer needed, then we remove the name from the register and
the register can be used to store some other names.
t1 : = 4 * i
t2 : = a [ t1 ]
t3 : = 4 * i
t4 : = b [ t3 ]
t5 : = t2 * t4
t6 : = prod + t5
prod : = t6
t7 : = i + 1
i : = t7
if i <= 20 goto B2
prod : = 0
i:=1
A SIMPLE CODE GENERATOR
 A code generator generates target code for a sequence of three- address statements and
effectively uses registers to store operands of the statements.
 For example: consider the three-address statement a := b+c
It can have the following sequence of codes:
ADD Rj, Ri Cost = 1 // if Ri contains b and Rj contains c
(or)
ADD c, Ri Cost = 2 // if c is in a memory location
(or)
MOV c, Rj Cost = 3 // move c from memory to Rj and add
ADD Rj, Ri
Register and Address Descriptors:
 A register descriptor is used to keep track of what is currently in each registers. The
register descriptors show that initially all the registers are empty.
 An address descriptor stores the location where the current value of the name can be
found at run time.
Input: Basic block B of three-address statements

Output: At each statement i: x= y op z, we attach to i the liveliness and next-uses of x, y and z.
Method: We start at the last statement of B and scan backwards.
1. Attach to statement i the information currently found in the symbol table regarding the next-use and
liveliness of x, y and z.
2. In the symbol table, set x to “not live” and “no next use”.
3. In the symbol table, set y and z to “live”, and next-uses of y and z to i.
A code-generation algorithm:
The algorithm takes as input a sequence of three-address statements constituting a basic block.
For each three-address statement of the form x : = y op z, perform the following actions:
1. Invoke a function getreg to determine the location L where the result of the computation y op
z should be stored.
2. Consult the address descriptor for y to determine y’, the current location of y. Prefer the
register for y’ if the value of y is currently both in memory and a register. If the value of y is not
already in L, generate the instruction MOV y’ , L to place a copy of y in L.
3. Generate the instruction OP z’ , L where z’ is a current location of z. Prefer a register to a
memory location if z is in both. Update the address descriptor of x to indicate that x is in location
L. If x is in L, update its descriptor and remove x from all other descriptors.
4. If the current values of y or z have no next uses, are not live on exit from the block, and are in
registers, alter the register descriptor to indicate that, after execution of x : = y op z , those
registers will no longer contain y or z.
Generating Code for Assignment Statements:
The assignment d : = (a-b) + (a-c) + (a-c) might be translated into the following three address
code sequence:
t:=a–b
u:=a–c
v:=t+u
d:=v+u
with d live at the end.
Code sequence for the example is:

CD UNIT V Basic Blocks

Uploaded by

Copyright:

Available Formats

CD UNIT V Basic Blocks

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

CD UNIT V Basic Blocks

Uploaded by

Copyright:

Available Formats

Basic Blocks

Basic Block Construction:

Algorithm: Partition into basic blocks

The three-address code for the above source program is given as

Basic block 1: Statement (1) to (2)

Transformations on Basic Blocks:

1. Structure preserving transformations:

prod : = 0 Basic Block B1

Input: Basic block B of three-address statements

You might also like