# Minimum number of registers needed to compile code segment without spills?

For the following 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;
}


All variables are assumed to be dead after this code segment. The only allowed compiler optimization is code motion, which moves statements from one place to another while preserving correctness, and each instruction can have at most two source operands and one destination operand.

The minimum number of spills to memory on a 2 register architecture for this code is 1, since c will have to be stored into memory, as it is not known if x > a or not. For this same code, with no other optimizations allowed besides register allocation, the minimum number of registers needed in the instruction set architecture to compile this code segment without any spills to memory during the compilation process is 4, but why is this?

• Do you mean "registers needed" for the compilation process, or by the generated code? – Raphael Sep 6 '16 at 8:25
• There is so much information missing from this question. The tags suggest that this is a question as much about code reordering as it is about register allocation. You also need to be clear about what variables are live on entry and exit to the fragment. – Pseudonym Sep 8 '16 at 23:46