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

Common data questions

Common Data for Questions 48 and 49:
The following code segment is executed on a processor which allows only register operands in its instructions. Each instruction can have atmost two source operands and one destination operand. Assume that all variables are dead after this code segment.

c = a + b;
d = c * a;
e = c + a;
x = c * c;
if (x > a) {
    y = a * a;
}
else {
    d = d * d;
    e = e * e;
}

Shared with question 48.

What is the minimum number of registers needed in the instruction set architecture of the processor to compile this code segment without any spill to memory? Do not apply any optimization other than optimizing register allocation.

Official answer and solution

Official answer: B
From: Official GATE 2013 answer key

Solution

Determine the maximum number of simultaneously live variables across the unmodified code segment to find the minimum number of registers needed without spilling.

Without code motion or any other optimizations, let us analyze the set of live variables after each statement:

After c = a + b: variables $a, c$ are live. (2 live variables)
After d = c * a: variables $a, c, d$ are live. (3 live variables)
After e = c + a: variables $a, c, d, e$ are live. (4 live variables)
After x = c * c: variable $c$ is no longer used, but $x$ is now computed. The live variables are $a, d, e, x$ . (4 live variables)
At the branch condition if (x > a): variables $d, e$ must be preserved for the else branch, while $x$ and $a$ are needed for the comparison. Hence, exactly 4 variables ( $a, d, e, x$ ) are simultaneously live.

Since the maximum number of simultaneously live variables is 4, the chromatic number of the register interference graph is 4. Therefore, at least 4 registers are required to execute this code without any memory spills.

This matches option (B).

Final answer

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

Source

Paper: GATE 2013 Computer Science and Information Technology (CS)
Question: 49 of 65, printed as CS Q.49
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.