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 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.
https://cs.nyu.edu/~gottlieb/courses/2000s/2006-07-fall/compilers/lectures/lecture-14.html [working link]
Correct Answer: $A$
isn't it right?
...........
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.
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))