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

is this in 2016 syllabus?

---

yes

---

NO , control-flow-graph or CFG is NOT in the syllabus for GATE 2017,

Control Flow Graphs comes under Code optimization phase which was previously in the syllabus as Basics of code optimization but from 2016 this part is out of syllabus.

---

@ravi_ssj4   are u sure this is not in syllabus of gate 2017 and tell me   gateoverflow.in/8084/gate2015-2_14   this i in syllabus or not  bcz abstract tree and control flow graph related to code optimization

---

Abstract Syntax Tree or AST is not just related to code optimization. It is a kind of Intermediate Code representation, so it is in syllabus.

Code Optimization is not in the 2017 syllabus as control flow graph (CGFs) are  related to code Optimization ,  hence  not in the syllabus.

---

CFG is NOT in the  2017 syllabus , from 2016 as per new syllabus it is removed.

---

syllabus is unreliable. its better to study on safer side

---

WHY 3..9 IS IN ONE NODE .IT SHOULD BE 3..8 AND 9TH STATEMENT IS DECISION STATEMENT SO IT SHOULD BE SEPRATED FROM NON-DESIONAL STATEMENTS ...SIMILARLY 10TH AND 11TH STATEMENTS SHOULD BE SEPRATED ...

---

@abhishek

I have 2 doubts in the above example from pic

1) why instruction 5 is in a different basic Block?

2) Since, instruction 7 is an unconditional branch, how can there be an edge to the EXIT block?

According to the rules the instruction 5 should come in the 3rd basic block. (Please correct me if I'm wrong)

And I'm not sure about the edge to EXIT block...

Please explain....

---

@Hopealways @abhishek bhardwaj 1 I don;t think the above posted question and solution by abhishek is correct
I am getting following basic blocks (1,2) (3,4,5) (6) (7),

how can $if(b<=a)$  be in a separate block?

---

@chauhansunil20th

yeah. Same here. And will there be an edge from the basic block containing the instruction no 7 to the EXIT BB??? (Since there is an unconditional jump from instruction 7 to instruction 3, it will be always taken and program will never EXIT).

Please clarify this

---

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

---

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.

---

Answe is 6,7

---

@princeit07 blocks 10 and 11 can be in the same block, right?

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

@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.

---

@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.

---

Good explanation

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

answer is b (6 and 7)