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

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

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

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.

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

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

here is correct control follow the diagram

0

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 ?

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)
answer is b (6 and 7)
answered by Active (1.4k points)
answered by Active (1.4k points)
0
How B explain Your Words

here is correct control follow the diagram

answered by Junior (527 points)

1
2