Here, we are told not to do code motion. So, we start with 3 registers
c = a + b; //a, c in register
d = c * a; //a, c, d in register
e = c + a; //a, c, e in register, d spilled.
So, now we try with 4 registers
c = a + b; //a, c in register
d = c * a; //a, c, d in register
e = c + a; //a, c, d, e in register
x = c * c; //a, x, d, e in register
if (x > a) {
y = a * a;
}
else {
d = d * d;
e = e * e;
}
No spilling. So, 4 is the minimum number of registers needed for avoiding spilling. (If code motion was allowed, we need only 3 registers for avoiding spilling).