GATE CSE 2015 | Set 2 | Question: 29

Question

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

• A. $5$ and $7$
• B. $6$ and $7$
• C. $5$ and $5$
• D. $7$ and $8$

Comments

as for as i know , Basic Block contains a sequence of instructions where there must have one entry and exit point.
so not all nodes are not basic block,while all basic blocks are nodes! if my understanding wrong, please do correct me !


source : Lec17-CFG-dataflow

---

thank you bro! @Amjad.

---

@vxi lin @Amjad. @Prime23 @Deepak Poonia
if its asked for "nodes and edges in control-flow-graph" then we  include Start and End , and if they ask for blocks then don't include them, since its mcq type so we can check but if its numerical type in that case there might be conflicts because different sources include or exclude start / end nodes 

https://web.stanford.edu/class/archive/cs/cs143/cs143.1128/lectures/15/Slides15.pdf (here its included) 


here its not included 
https://www.csl.cornell.edu/~zhiruz/5997/pdf/lecture04.pdf

 

Answer 1

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. 

Comments

@Deepak Poonia Thanks sir 🙏 the doubt cleared. 

---

@Deepak Poonia Nice explanation sir

 

---

The basic block 10 11 have two edges exiting that block but defn of basic block says that it must have only one entry and exit edges ???

Answer 2

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 .

Answer 3

 4 NODES 5-edges

and if we add start and end nodes then

6-nodes and 7-edges

Comments

CHECK IT NOW

---

Thank U

---

@Tauhin sir , can u give me some questions or link related to this question for practice ??

Answer 4

1. First statement is a leader. 2.target of go to is leader. 3.next statement of goto is leader. so

1.leader.

2.leader.

3.leader

10.leader.

now there will be 4 basic blocks made out of it.

Add start and stop to these four blocks.

Also number for nodes would be 6.and edges would be 7..

 

1 is b1.

2 is b2.

3-9 is b3

10-11 is b4

Answer 5

here is correct control follow the diagram

 

Answer 6

answer is b (6 and 7)