Consider the basic block given below. a = b + c c = a + d d = b + c e = d - b…
2014
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
Attempted by 19 students.
Show answer & explanation
Correct answer: A
In the DAG representation of the basic block, algebraic simplifications minimize the structure by recognizing value equivalences:
After a = b + c and c = a + d, we have c = b + c + d (initial values).
Then d = b + c gives d = 2b + c + d.
For e = d - b, this simplifies to e = (2b + c + d) - b = b + c + d, which equals the current value of c.
For a = e + b, this simplifies to a = (b + c + d) + b = 2b + c + d, which equals the current value of d.
Thus, no new nodes are needed for e or the final a; they reuse existing nodes.
The minimized DAG has:
3 leaf nodes: initial b, c, d.
3 internal nodes: one for b + c, one for that plus d, and one for b plus the second result.
With 3 binary operators, there are 6 edges (2 per operator).