Official PYQ · 2013Q49Local OptimizationMCQ1 mark

GATE CS 2013 Q49 — Local Optimization

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; 
}

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.

View worked solution

Answer: B

To find the minimum number of registers required without any memory spill, we analyze the liveness of variables at each step of the code segment:

Initially: $a$ and $b$ must be in registers. Let $R_1 = a$ and $R_2 = b$ .
c = a + b;
Since $b$ is dead after this instruction, we can reuse its register for $c$ .
Live variables: $a, c$ → Register assignment: $R_1 = a$ , $R_2 = c$ .
d = c * a;
We need a new register for $d$ because $d$ is used later in the else block.
Live variables: $a, c, d$ → Register assignment: $R_1 = a$ , $R_2 = c$ , $R_3 = d$ .
e = c + a;
We need a new register for $e$ because $e$ is used later in the else block.
Live variables: $a, c, d, e$ → Register assignment: $R_1 = a$ , $R_2 = c$ , $R_3 = d$ , $R_4 = e$ .
x = c * c;
Since $c$ is dead after this instruction, we can reuse its register for $x$ .
Live variables: $a, d, e, x$ → Register assignment: $R_1 = a$ , $R_2 = x$ , $R_3 = d$ , $R_4 = e$ .

At the point right before x = c * c, the four variables $a, c, d,$ and $e$ are simultaneously live, which requires at least 4 registers. As shown in the step-by-step allocation, 4 registers are also sufficient to complete the execution of both branches without any spill.

Free practice · Your answers on this page are not saved.

Published 10 Oct 2026

Report a correction

More Local Optimization questions

GATE CS 2013 Q49 — Local Optimization

Related questions