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