Andrey Penechko.
Linear scan register allocation pass
Notes:
Non-split current interval does not intersect with inactive intervals because of SSA form
Splits need to be at the odd position. This gives:
a) no intervals of form: [x; x)
b) no problems with two operand form mov instruction before two operand instruction
two operand form can insert mov from first operand into result register
and in case first operand's interval was split it would start at the instruction and not include the mov
as result register allocator may allocate arg0 register to reloaded argument,
but reload will precede the mov, thus overwriting the value
100 | v0 = add v1, v2 | eax(v0) = add ecx(v1), ecx(v2)
v0 [100; 200) eax
v1 [50; 100) ecx
v2 [40; 99) s0 [100; 109) ecx
becomes
99| ecx = load i32* s3 // split move overwrites ecx that is used in the next instruction
99| eax = mov ecx // fix two operand form
100| eax = add eax, ecx
As result of splits being on odd positions another invariant becomes available:
All ranges have distinct from and to positions. Zero length ranges become impossible.
range.from < range.to