Applied Test Series

Question

Consider the following code

 

1.  location = -1

2.  i=0

3.  if (i<100) goto 5

4.  goto 13

5.  t1 = 4*i

6.  go to 3

7.  t2 = A[t1]

8.  if t2 = x goto 10

9.  goto 11

10.location = i

11.t3 = i+1

12.i = t3

13.goto 3

 

The number of basic blocks from the given code are______

Comments

the number of leaders in given basic block =$9$, please verify it.

---

Yes sir ,the number of leaders in given control flow graph =9, which are 1,3,4,5,7,9,10,11,13.

Answer 1

Basic block: The collection of 3AC statements from leader to next leader without including the next leader is known as the basic block. 

Steps to find the basic blocks:

• Identify the leader first. (The first statement of 3AC is the leader.)
• Address of conditional, unconditional goto is the leader. (target location of goto)
• immediate next line of goto is the leader.

Now construct the basic block from leader to line before the next leader.

In the given 3AC $9$ leaders are there: $1,3,4,5,7,9,10,11,13$

There are $9$ basic block are there:

1. Block $B_1$: statement $1-2$
2. Block $B_2$: statement $3$
3. Block $B_3$: statement $4$
4. Block $B_4$: statement $5-6$
5. Block $B_5$: statement $7-8$
6. Block $B_6$: statement $9$
7. Block $B_7$: statement $10$
8. Block $B_8$: statement $11-12$
9. Block $B_9$: statement $13$

Ref: Basic Block

Answer 2

A number of basic blocks = Number of leaders. Because every basic block will contain 1 leader.

Now, how to find a leader?

1. The first statement is a leader.
2. The target of a goto is a leader.
3. The next statement after goto is a leader.

So here in this question the number of leaders in the given control flow graph =9, which are 1,3,4,5,7,9,10,11,13.

The number of basic blocks from the given code is =9.