更新时间:2023-10-17 17:14:10
According to this paper (in section 7), the linear scan register allocation algorithm needs to reserve a scratch register.
This has a negative effect on architectures with few registers such as the Intel IA-32 architecture because it increases the register pressure. In particular, it is not possible to implement the algorithm without reserving a scratch register: When a spilled interval is used by an instruction requiring the operand in a register, the interval must be temporarily reloaded to the scratch register.
Let's say you have the following assembly and 3 registers:
mov t1, 1
mov t2, 2
mov t3, 3
mov t4, 4
mov t5, 5
add t4, t5
push t1
push t2
push t3
push t4
push t5
You'll assign the first two registers (keeping the third one for spilling):
mov r1, 1
mov r2, 2
mov r3, 3
mov [sp + 4], r3
mov r3, 4
mov [sp + 8], r3
mov r3, 5
mov [sp + 12], r3
mov r3, [sp + 8]
add r3, [sp + 12]
push r1
push r2
mov r3, [sp + 4]
push r3
mov r3, [sp + 8]
push r3
mov r3, [sp + 12]
push r3
There seem to be an alternative not requiring a scratch register, which is called splitting, but I have not investigated it yet, but the aforementioned paper describes it.
Another idea would be to use a different algorithm that re-run itself with the new instructions generated by spilling and using a spill heuristic that will spill longer ranges, so that the new temporaries generated by spilling won't be spilled again.