19,216 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$

@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

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.

by

here is correct control follow the diagram

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 ?

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.

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 .

by

4 NODES 5-edges

and if we add start and end nodes then

6-nodes and 7-edges

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