Consider the basic block given below.a = b + c c = a + d d = b + c e = d - b a = e + bThe minimum number of nodes and edges present in the DAG representation of the above basic block respectively are

Let us construct the Directed Acyclic Graph (DAG) for the basic block:

1. a = b + c

   • Leaf nodes: $b_0$, $c_0$

   • Node $n_1 = (+, b_0, c_0)$, labeled $\{a_1\}$ (2 edges)

2. c = a + d

   • Leaf node: $d_0$

   • Node $n_2 = (+, n_1, d_0)$, labeled $\{c_1\}$ (2 edges)

3. d = b + c

   • Node $n_3 = (+, b_0, n_2)$, labeled $\{d_1\}$ (2 edges)

4. e = d - b

   • Since $d = b + c_1$, the expression $e = d - b = (b + c_1) - b = c_1$.

   • Thus, $e$ evaluates to the value represented by node $n_2$, so label $e$ is attached to $n_2$.

5. a = e + b

   • Since $e$ is $n_2$, $e + b = n_2 + b_0 = b_0 + n_2$, which is already computed at node $n_3$.

   • Thus, the new value of $a$ is attached to node $n_3$.

Total Nodes:

• 3 leaf nodes: $b_0, c_0, d_0$

• 3 interior operation nodes: $n_1 (+), n_2 (+), n_3 (+)$

• Total nodes = $3 + 3 = 6$

Total Edges:

• $n_1 \to b_0, c_0$ (2 edges)

• $n_2 \to n_1, d_0$ (2 edges)

• $n_3 \to b_0, n_2$ (2 edges)

• Total edges = $2 + 2 + 2 = 6$

Therefore, the minimum number of nodes and edges is 6 and 6, which corresponds to option (A).