最近在调查寄存器spill性能影响过程中，遇到了一个关于寄存器分配顺序问题，所以特地去研究了LLVM中物理寄存器分配顺序的具体实现。

问题起因是，在当前研究的架构中存在几个硬体自动保存的寄存器，也就是说，函数调用及返回过程中，硬体会自动保存和恢复这几个物理寄存器。很显然，在调用ABI设计中，将这几个寄存器直接设置成为Callee save寄存器。但是LLVM编译器在寄存器分配的过程中，总是将这几个寄存器的分配顺序放在很后面，导致某些性能函数caller save寄存器大量发生spill，没有很好的利用硬体保存恢复这部分寄存器的特性。

通过分析，基本可以确认，LLVM中寄存器的分配顺序由三个因素决定：

1、由寄存器td文件中寄存器定义顺序决定：

以aarch64为例，64位物理寄存器初始顺序为：

X0，X1，X2... ... X28，FP，LR

def GPR64common : RegisterClass<"AArch64", [i64], 64,
(add (sequence "X%u", 0, 28), FP, LR)> {
let AltOrders = [(rotl GPR64common, 8)];
let AltOrderSelect = [{ return 1; }];
}

同时，AltOrders会提供另外一种可选的寄存器分配顺序（rotl GPR64common, 8）：

X8，X9... ... X28，FP，LR，X0，X1... ... X7

在aarch64中X0~X7为入参及返回寄存器，所以AltOrders定义的寄存器顺序非常合理。

最后在寄存器分配过程中选择初始分配顺序还是AltOrders定义的顺序由AltOrderSelect中的代码片段决定，GPR64common中AltOrderSelect始终返回1，所以64位物理寄存器分配顺序由AltOrders决定。

2、由RegisterClassInfo中的compute函数决定：

以上面第一步中获取的寄存器顺序（getRawAllocationOrder）为基础，将CSR寄存器，也就是callee saved寄存器移到最后，所以compute计算结束后的寄存器分配顺序为：

X8，X9... ... X18，X0，X1... ... X7，FP，LR，X19，X20... ... X28

其中，FP，LR，X19，X20... ... X28为Callee Saved寄存器。

/// compute - Compute the preferred allocation order for RC with reserved
/// registers filtered out. Volatile registers come first followed by CSR
/// aliases ordered according to the CSR order specified by the target.
void RegisterClassInfo::compute(const TargetRegisterClass *RC) const {
... ...
ArrayRef<MCPhysReg> RawOrder = RC->getRawAllocationOrder(*MF);
for (unsigned i = 0; i != RawOrder.size(); ++i) {
unsigned PhysReg = RawOrder[i];
// Remove reserved registers from the allocation order.
 if (Reserved.test(PhysReg))
continue;
unsigned Cost = TRI->getCostPerUse(PhysReg);
MinCost = std::min(MinCost, Cost);

if (CSRNum[PhysReg])
// PhysReg aliases a CSR, save it for later.
 CSRAlias.push_back(PhysReg);
else {
if (Cost != LastCost)
LastCostChange = N;
RCI.Order[N++] = PhysReg;
LastCost = Cost;
}
}
RCI.NumRegs = N + CSRAlias.size();
assert (RCI.NumRegs <= NumRegs && "Allocation order larger than regclass");

// CSR aliases go after the volatile registers, preserve the targets order.
 for (unsigned i = 0, e = CSRAlias.size(); i != e; ++i) {
unsigned PhysReg = CSRAlias[i];
unsigned Cost = TRI->getCostPerUse(PhysReg);
if (Cost != LastCost)
LastCostChange = N;
RCI.Order[N++] = PhysReg;
LastCost = Cost;
}

很显然，本人遇到问题的罪魁祸首就是这个compute函数。

3、实际的寄存器分配过程中（LLVM在O0场景使用FastAlloc，O2及以上的场景使用GreedyAlloc分配演算法），调用AllocationOrder类函数决定最终的寄存器分配顺序：

其中RegClassInfo.getOrder函数会返回上面第二步中获得的分配顺序结果，最后再调用getRegAllocationHints函数获取最终的寄存器分配顺序结果。

// Compare VirtRegMap::getRegAllocPref().
AllocationOrder::AllocationOrder(unsigned VirtReg,
const VirtRegMap &VRM,
const RegisterClassInfo &RegClassInfo,
const LiveRegMatrix *Matrix)
: Pos(0) {
const MachineFunction &MF = VRM.getMachineFunction();
const TargetRegisterInfo *TRI = &VRM.getTargetRegInfo();
Order = RegClassInfo.getOrder(MF.getRegInfo().getRegClass(VirtReg));
TRI->getRegAllocationHints(VirtReg, Order, Hints, MF, &VRM, Matrix);
rewind();
... ...
}

当前LLVM所有后端架构中，只有Arm32重新实现了这个介面函数，从函数内容来看，实现了奇偶寄存器对的分配问题（由于本人对Arm32架构不是很熟悉，Arm32中的Hints函数细节了解的不是很清楚）。但从LLVM默认的getRegAllocationHints介面实现来看，这个函数主要用于帮助寄存器分配器消除一些不必要的copy指令，比如函数入参在做lowering过程中，一般都会生成入参物理寄存器到虚拟寄存器的copy指令，其实这些copy指令完全是多余，所以hints函数会将这些虚拟寄存器直接指定为对应的入参物理寄存器。

/// Get a list of hint registers that the register allocator should try
 /// first when allocating a physical register for the virtual register
 /// VirtReg. These registers are effectively moved to the front of the
 /// allocation order.
 ///
 /// The Order argument is the allocation order for VirtRegs register class
 /// as returned from RegisterClassInfo::getOrder(). The hint registers must
 /// come from Order, and they must not be reserved.
 ///
 /// The default implementation of this function can resolve
 /// target-independent hints provided to MRI::setRegAllocationHint with
 /// HintType == 0. Targets that override this function should defer to the
 /// default implementation if they have no reason to change the allocation
 /// order for VirtReg. There may be target-independent hints.
 virtual void getRegAllocationHints(unsigned VirtReg,
ArrayRef<MCPhysReg> Order,
SmallVectorImpl<MCPhysReg> &Hints,
const MachineFunction &MF,
const VirtRegMap *VRM = nullptr,
const LiveRegMatrix *Matrix = nullptr)
const;

通过上述的分析，到目前为止，还是无法找到行之有效的解决方案（只通过修改后端相关代码），只能通过改写RegisterClassInfo中的compute来暂时规避这个问题。

当然，我也会向社区反馈寻求解决这个问题更好的方法。寄存器分配问题一直以来都是编译器领域尤其是中后端编译优化领域的一个可以持续探讨和改进的课题，问题本身很有意思，也可以衍生出各种优化策略，后面有时间的话，再写写关于寄存器压力评估，寄存器spill问题优化遇到的一些有意思的场景。

推荐阅读：

相关文章