GATE CSE 2014 | Set 3 | Question: 34

Question

Consider the basic block given below. 

a = b + c 
c = a + d 
d = b + c 
e = d - b 
a = e + b 

The minimum number of nodes and edges present in the DAG representation of the above basic block respectively are

• A. $6$ and $6$
• B. $8$ and $10$
• C. $9$ and $12$
• D. $4$ and $4$

Comments

Yeah it is in syllabus. Question can be asked from anywhere if it is even a little bit in syllabus. So leave recent out of syllabus topics carefully.

---

It is in syllabus now, i.e for 2021 onwards.

---

 

The answer is 6,6 If it asks for minimal as we need to do the modification.

The answer will be 8 and 10 if they ask for normal DAG without modifcation.

 

 

Answer 1

A normal DAG construction will give $8$ nodes and $10$ edges as shown below.

Since, this question asks for minimum possible, we can assume algebraic simplification is allowed. So, $d = b + c, e = d - b$; can be simplified to $d = b + c$; $e = c$; Similarly, $e = d - b$; $a = e + b$; can be simplified to $a = d$. This gives the following DAG with $6$ nodes and $6$ edges.

Reference: https://cs.nyu.edu/~gottlieb/courses/2000s/2006-07-fall/compilers/lectures/lecture-14.html

Correct Answer: $A$

Comments

@shefali1 in your written question is wrong bcoz in que a= b+c but you written it 

a=b+e 

---

There is no such thing as “Normal DAG” and “minimal DAG” representation of a Basic Block, The substitution method that they have used to get the answer as (6,6) does not exist in any canonical texts, There is only one method to create DAGs for Basic Blocks and it is given in the book “Compilers by Aho, Lam, ,Sethi, Ullman Second Edition Page 533”, The document that you have linked is just a copy paste from this book. If they wanted us to use substitution then they should have mentioned that all the variables except the last one are temporary variables which are not live after the Block since thats the only case you can reduce statements in a three address basic block using operator associativity and commutative properties to maintain semantics but they haven’t mentioned any such thing. They can’t even formulate questions without ambiguity, I think they do it on purpose in order to introduce the chance factor for deciding ranks. Its a rotten system of evaluation. 

---

Is this DAG is right ?

Answer 2

6,6 is the answer.

 

Comments

@ananya_23 Will it be sufficient to draw DAG for only a1? We have to draw for a0,c1,d1,e0 also right ! 

---

@Souvik33 how can you initially calculate b0+b0..? so we wont be able to derive c1,a0...??
i feel this is wrong. Please Correct me, if i am missing something 

---

this approach is wrong.You can find it difficult to solve other problem with this approach.

Answer 3

Best approach of doing this question is "Go in reverse order". and it has asked for minimum so we can simplify wherever possible.

A = (E+B)

((D-B)+B) = (D) Because both + , - has same precedence

(B+C)

(B+(A+D))

(B+((B+C)+D))

 

Comments

@Nitesh Singh 2

How you put the bracket?

---

Brackets are just to indicate "appropriate value has been substituted in place of the previous variable".

---

I found this super easy, can we use this for any questions of similar kind?

---

@Nitesh Singh 2 Sir, Do we only need to find the expression for the final variable value given in the basic block (i.e A here) ? Please tell !

Answer 4

Simplifying the given equations : 
 
d = b + c (given) e = d – b (given) => d = b + c and e = c 
 
e = d - b (given) a = e + b (given) => a = d 
 
 
 
Thus, the given DAG has 6 nodes and 6 edges. 

Answer 5

A

Answer 6

Reposting the answer by @princeit07