GATE CS 2021 Set 1 Q50 — Local Optimization

To find the number of nodes in the Directed Acyclic Graph (DAG) for the given basic block, we construct the DAG step-by-step by identifying common subexpressions and reusing existing nodes.

1. a = b + c:
   • Create leaf nodes for variables b and c.
   • Create an operator node + with children b and c. Label this node with a.
   • Nodes created: {b, c, +a} (3 nodes)
2. e = a + 1:
   • Create a leaf node for constant 1.
   • Create an operator node + with children +a and 1. Label this node with e.
   • Nodes created: {1, +e} (2 new nodes, total 5)
3. d = b + c:
   • The expression b + c is already represented by the node +a.
   • We simply add the label d to this existing node.
   • Nodes created: 0 (total 5)
4. f = d + 1:
   • Since d and a refer to the same node, d + 1 is equivalent to a + 1, which is already represented by the node +e.
   • We add the label f to the node +e.
   • Nodes created: 0 (total 5)
5. g = e + f:
   • Create an operator node + where both the left and right children point to the node labeled e, f. Label this node with g.
   • Nodes created: {+g} (1 new node, total 6)

The final DAG consists of the following 6 nodes:

1. Leaf node b
2. Leaf node c
3. Operator node + (labeled a, d)
4. Leaf node 1
5. Operator node + (labeled e, f)
6. Operator node + (labeled g)