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

Dark Mode

19,216 views

37 votes

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

- $5$ and $7$
- $6$ and $7$
- $5$ and $5$
- $7$ and $8$

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.

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.

0

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

1

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.

1

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

3 votes