in Compiler Design
229 views
1 vote
1 vote

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______

in Compiler Design
by
229 views

2 Comments

the number of leaders in given basic block =$9$, please verify it.
0
0
Yes sir ,the number of leaders in given control flow graph =9, which are 1,3,4,5,7,9,10,11,13.
1
1

2 Answers

2 votes
2 votes
Best answer

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

selected by
4 votes
4 votes

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.