## Three Address Code | DAGs | Basic Blocks & Flow Graphs-

Before you go through this article, make sure that you have gone through the previous articles on-

In this article, we will solve Miscellaneous Problems based on these Concepts.

## Problem-01:

Generate three address code for the following code-

c = 0

do

{

if (a < b) then

x++;

else

x–;

c++;

} while (c < 5)

## Solution-

Three address code for the given code is-

1. c = 0
2. if (a < b) goto (4)
3. goto (7)
4. T1 = x + 1
5. x = T1
6. goto (9)
7. T2 = x – 1
8. x = T2
9. T3 = c + 1
10. c = T3
11. if (c < 5) goto (2)

## Problem-02:

Generate three address code for the following code-

while (A < C and B > D) do

if A = 1 then C = C + 1

else

while A <= D

do A = A + B

## Solution-

Three address code for the given code is-

1. if (A < C) goto (3)
2. goto (15)
3. if (B > D) goto (5)
4. goto (15)
5. if (A = 1) goto (7)
6. goto (10)
7. T1 = c + 1
8. c = T1
9. goto (1)
10. if (A <= D) goto (12)
11. goto (1)
12. T2 = A + B
13. A = T2
14. goto (10)

## Problem-03:

Generate three address code for the following code-

switch (ch)

{

case 1 : c = a + b;

break;

case 2 : c = a – b;

break;

}

## Solution-

Three address code for the given code is-

if ch = 1 goto L1

if ch = 2 goto L2

L1:

T1 = a + b

c = T1

goto Last

L2:

T1 = a – b

c = T2

goto Last

Last:

## Problem-04:

Construct a DAG for the following three address code-

1. a = b + c
2. t1 = a x a
3. b = t1 + a
4. c = t1 x b
5. t2 = c + b
6. a = t2 + t2

## Solution-

Directed acyclic graph for the given three address code is-

## Problem-05:

Consider the following code-

prod = 0 ;

i = 1 ;

do

{

prod = prod + a[ i ] x b[ i ] ;

i = i + 1 ;

} while (i <= 10) ;

1. Compute the three address code.
2. Compute the basic blocks and draw the flow graph.

## Solution-

### Part-01:

Three address code for the given code is-

prod = 0

i = 1

T1 = 4 x i

T2 = a[T1]

T3 = 4 x i

T4 = b[T3]

T5 = T2 x T4

T6 = T5 + prod

prod = T6

T7 = i + 1

i = T7

if (i <= 10) goto (3)

### Step-01:

We identify the leader statements as-

• prod = 0 is a leader because first statement is a leader.
• T1 = 4 x i is a leader because target of conditional or unconditional goto is a leader.

### Step-02:

The above generated three address code can be partitioned into 2 basic blocks as-

### Step-03:

The flow graph is-

To gain better understanding about these Miscellaneous Problems,

Watch this Video Lecture

Next Article- Code Optimization

Get more notes and other study material of Compiler Design.

Watch video lectures by visiting our YouTube channel LearnVidFun.

## Basic Blocks-

 Basic block is a set of statements that always executes in a sequence one after the other.

The characteristics of basic blocks are-

• They do not contain any kind of jump statements in them.
• There is no possibility of branching or getting halt in the middle.
• All the statements execute in the same order they appear.
• They do not lose lose the flow control of the program.

### Example Of Basic Block-

Three Address Code for the expression a = b + c + d is-

Here,

• All the statements execute in a sequence one after the other.
• Thus, they form a basic block.

### Example Of Not A Basic Block-

Three Address Code for the expression If A<B then 1 else 0 is-

Here,

• The statements do not execute in a sequence one after the other.
• Thus, they do not form a basic block.

## Partitioning Intermediate Code Into Basic Blocks-

Any given code can be partitioned into basic blocks using the following rules-

### Rule-01: Determining Leaders-

Following statements of the code are called as Leaders

• First statement of the code.
• Statement that is a target of the conditional or unconditional goto statement.
• Statement that appears immediately after a goto statement.

### Rule-02: Determining Basic Blocks-

• All the statements that follow the leader (including the leader) till the next leader appears form one basic block.
• The first statement of the code is called as the first leader.
• The block containing the first leader is called as Initial block.

## Flow Graphs-

 A flow graph is a directed graph with flow control information added to the basic blocks.

• The basic blocks serve as nodes of the flow graph.
• There is a directed edge from block B1 to block B2 if B2 appears immediately after B1 in the code.

## Problem-01:

Compute the basic blocks for the given three address statements-

(1) PROD = 0

(2) I = 1

(3) T2 = addr(A) – 4

(4) T4 = addr(B) – 4

(5) T1 = 4 x I

(6) T3 = T2[T1]

(7) T5 = T4[T1]

(8) T6 = T3 x T5

(9) PROD = PROD + T6

(10) I = I + 1

(11) IF I <=20 GOTO (5)

### Solution-

We have-

• PROD = 0 is a leader since first statement of the code is a leader.
• T1 = 4 x I is a leader since target of the conditional goto statement is a leader.

Now, the given code can be partitioned into two basic blocks as-

## Problem-02:

Draw a flow graph for the three address statements given in problem-01.

## Solution-

• Firstly, we compute the basic blocks (already done above).
• Secondly, we assign the flow control information.

The required flow graph is-

To gain better understanding about Basic Blocks and Flow Graphs,

Watch this Video Lecture