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?
will @shefali1 method will always give correct result??
because it seems bit easy draw DAG from reverse.
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
@Nitesh Singh 2
How you put the bracket?
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.