7.6k 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 | 7.6k views
+5
is this in 2016 syllabus?
–1
yes
+20

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.

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

+6

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

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

by Veteran (434k points)
selected
0
+8
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

+4
6, 7 is correct and that is given in answer key too.
+2

here is correct control follow the diagram

+1

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 ?

0

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 Loyal (9.9k points)
answer is b (6 and 7)
by Active (1.4k points)
by Active (1.4k points)
0

here is correct control follow the diagram

by Junior (647 points)