in Compiler Design edited by
19,216 views
37 votes
37 votes

Consider the intermediate code given below.

(1) i=1    
(2) j=1    
(3) t1 = 5 * i    
(4) t2 = t1 + j    
(5) t3 = 4 * t2    
(6) t4 = t3    
(7) a[t4] = -1    
(8) j = j + 1    
(9) if j <= 5 goto (3)    
(10) i = i +1    
(11) if i < 5 goto (2)

The number of nodes and edges in control-flow-graph constructed for the above code, respectively, are

  1. $5$ and $7$
  2. $6$ and $7$
  3. $5$ and $5$
  4. $7$ and $8$
in Compiler Design edited by
19.2k views

4 Comments

@Hopealways yes you're right, i initially didn't notice it. it's unconditional jump.

0
0
1. 5 should be along with 34 in same block.

2. Logically, line-7 is wrong. How is i = i -1 and goto 3 in same line. It doesn't make sense. And even if we try to make some sense out of it, we can get 6 nodes and 6 edges, considering respective basic blocks: [Start, 12, 345, 6, 7, End] and edges without including an edge from 7->end.
0
0

Answe is 6,7

0
0

6 Answers

60 votes
60 votes
Best answer

Answer is $6,7$ if we add an explicit start and end nodes. This follows from the definition of CFG in the below IITM link

http://www.cse.iitm.ac.in/~krishna/cs3300/pm-lecture1.pdf

But many of the standard books/universities don't follow this definition. 

edited by
by

4 Comments

here is correct control follow the diagram

3
3

@Arjun 

Sir is this Control Flow Graph wrong ?

My doubt is that should we defenitely include start and end nodes and it's edges while calculating the number of edges and nodes ?

Please clarify.

1
1

@pranay562, @Raja Rawal

Answer provided by Arjun sir is correct.

Look if you closely look at the definition of Basic blocks : A basic block is a straight-line code sequence with no branches in except to the entry and no branches out except at the exit.(Source : Wikipedia)

Although your CFG(Control Flow Graph) is right according to the definition but why are you taking statement 9 or statement 10 as separate basic block ?

I mean if you take statement 3 to 9 in one basic block and statement 10 & 11 in one basic block then also the definition of basic block satisfies. I was also doing the same mistake. We have to make a basic block as large as possible.

1
1
7 votes
7 votes

Following are the Candidates for leader :

1.. First statement is a leader 

2. the target of unconditional and conditional instruction is a leader 

3. Statement following  unconditional and conditional instruction is a leader .

So let us count number of nodes :

Node1 :statement 1 

node 2 : Statement 2 

Node 3 : Statement 3 

node 4 : statement 4--9 

node 5 : Statement 10-11

Plus if i add one start and end nodes 

So in all there will be 7 nodes 

And the number of edges : 

We know that in a simple  connected graph with n nodes we have n-1 edges,

So here with 7 nodes we would have 6 edges + 2 edges ( GOTO 3 and GOTO 2--->backedges  ) = 8 edges .

3 votes
3 votes

 4 NODES 5-edges

and if we add start and end nodes then

6-nodes and 7-edges

edited by

4 Comments

CHECK IT NOW
1
1
Thank U
0
0
@Tauhin sir , can u give me some questions or link related to this question for practice ??
0
0
0 votes
0 votes
answer is b (6 and 7)
Answer:

Related questions