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.

**BASIC BLOCKS AND FLOW GRAPHS**

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 statementis 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:

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 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 + c - - > a
: = b + c

b
: = a - d - - > b
: = a - d

c
: = b + c - - > c : = b + c

d
: = a - d - - > d
: = 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
basic block 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 initial node.

•
E.g.: Flow graph for the vector dot
product is given as follows:

**Fig.
4.2 Flow graph for program**

• 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 from B1 (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

1.
All nodes in the collection are strongly
connected.

2.
The collection of nodes has a unique
entry.

• A loop that contains no other loops is called an
inner loop.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

**Related Topics **

Copyright © 2018-2021 BrainKart.com; All Rights Reserved. (BS) Developed by Therithal info, Chennai.