GATE CS 2011 Q.36 (CS Q.36): Intermediate Code Generation, Data Flow Analysis and Code Optimization

Consider evaluating the following expression tree on a machine with load-store architecture in which memory can be accessed only through load and store instructions. The variables $a, b, c, d$ and $e$ are initially stored in memory. The binary operators used in this expression tree can be evaluated by the machine only when the operands are in registers. The instructions produce result only in a register. If no intermediate results can be stored in memory, what is the minimum number of registers needed to evaluate this expression?

Expression tree with root plus, left child minus with operands a and b, and right child minus with operand e and right subtree plus of c and d

Official answer and solution

Official answer: D
From: Official GATE 2011 answer key

Solution

Apply the Sethi-Ullman algorithm to determine the minimum number of registers required for expression evaluation.

Under load-store architecture with binary operations occurring only between registers, the Sethi-Ullman labeling $L(n)$ for expression tree nodes is defined as:

For leaf node $x$ stored in memory: $L(x) = 1$ (needs 1 register to load).
For an interior binary node with children $l$ and $r$ :

L(n) = \begin{cases} \max(L(l), L(r)) & \text{if } L(l) \ne L(r) \\ L(l) + 1 & \text{if } L(l) = L(r) \end{cases}

Compute labels from bottom up:

Leaf nodes $a, b, c, d, e$ : each has label $1$ .

Evaluate subtrees:

Left - node $(a - b)$ : children $a$ and $b$ both have label 1, so $L(-_1) = 1 + 1 = 2$ .
Inner + node $(c + d)$ : children $c$ and $d$ both have label 1, so $L(+_2) = 1 + 1 = 2$ .
Right - node $(e - (c + d))$ : left child $e$ has label 1, right child $(c + d)$ has label 2. Since $L(l) \ne L(r)$ , $L(-_2) = \max(1, 2) = 2$ .

Root + node: left child has label 2 and right child has label 2. Since both children have equal label 2, the root label is:

L(\text{root}) = 2 + 1 = 3

Thus, evaluating one subtree requires 2 registers while holding its result in 1 register, and evaluating the other subtree simultaneously requires 2 registers, totaling $1 + 2 = 3$ registers minimum.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2011 Computer Science and Information Technology (CS)
Question: 36 of 65, printed as CS Q.36
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source