The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+25 votes
6.2k views

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
asked in Compiler Design by Veteran (97.7k points)
retagged by | 6.2k views
+4
is this in 2016 syllabus?
–1
yes
+15

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.

+2
@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
+6

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.

+4

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

+3
syllabus is unreliable. its better to study on safer side
0

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 ...LOOK AT THEIR SOLUTION ->MADE EASY

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

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

0

@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

0

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

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.

5 Answers

+37 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. 

answered by Veteran (414k points)
selected by
0
@suraj Can you please check?
+6
There are only two right choices for the given question (4, 5) (if we do not consider start and end vertices) and (6, 7) (if we consider start and end vertices). Since here (4,5) is not given in the options, therefore correct answer would be (6, 7).
+1
Answer 6 and 7 should be correct because end state is necessary to merge control from different blocks. check this



pls correct me if i am not.
0

what they have given in the official keys ? Question looks ambiguous to me sad

+3
6, 7 is correct and that is given in answer key too.
0

here is correct control follow the diagram

0

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

+4 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 .

answered by Loyal (9.6k points)
0 votes
answer is b (6 and 7)
answered by Active (1.4k points)
0 votes
answer is b
answered by Active (1.4k points)
0
How B explain Your Words
0 votes

here is correct control follow the diagram

 

answered by Junior (527 points)
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,814 questions
54,521 answers
188,388 comments
75,423 users