且构网

分享程序员开发的那些事...
且构网 - 分享程序员编程开发的那些事

如何处理多个溢出值作为单个指令的操作数?

更新时间: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.