如何处理多个溢出值作为单个指令的操作数？ [英] How to deal with multiple spilled values as operands for a single instruction?

问题描述

我要实现（在第7节中），线性扫描寄存器分配算法需要保留一个暂存寄存器。

这对寄存器较少的体系结构（如Intel IA-32体系结构）产生负面影响，因为它增加了寄存器压力。特别是，如果不保留暂存寄存器，就不可能实现该算法：当溢出的间隔被需要寄存器中操作数的指令使用时，该间隔必须暂时重新加载到暂存寄存器中。

假设您具有以下程序集和3个寄存器：

  mov t1，1 
 mov t2，2 
 mov t3，3 
 mov t4，4 
 mov t5，5 
加t4，t5 
推t1 
推t2 
推t3 
推t4 
推t5 
  

您将分配前两个寄存器（保留第三个寄存器以防溢出）：

  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] 
加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 
  

似乎有一种不需要暂存器的替代方法，称为拆分，但我尚未对此进行研究，但上述论文对此进行了描述。

另一个想法是使用一种不同的算法，该算法根据溢出产生的新指​​令重新运行自身，并使用将溢出更长范围的溢出试探法，从而不会产生由溢出产生的新临时变量再次溢出。

I want to implement the Linear Scan Register Allocation algorithm proposed by Poletto and Sarkar. It is pretty straight-forward and assigns either a register or a stack location to every live interval.

A stack location is only assigned to an interval when the number of active intervals that have been assigned registers is equal to the number of registers (i.e. there are no more free registers).

The algorithm:

Suppose an x86 instruction add a, b where a and b are variables that have both been assigned a stack location (spilled) by this algorithm. There is no way to encode this instruction with two memory operands, so at least one of the operands must reside in a register. I would insert a mov REG, a before the instruction, but as I understand the algorithm there are no free registers at this point in the code. How is this typically solved?

解决方案

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.

这篇关于如何处理多个溢出值作为单个指令的操作数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！