The Gateway to Computer Science Excellence

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

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

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

Please explain....

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

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

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.

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

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

pls correct me if i am not.

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

Please clarify.

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.

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.6k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,833 questions

57,718 answers

199,440 comments

107,764 users