LLVM 贪婪寄存器分配器（RAGreedy）详细处理流程
日期: 2025年5月29日
摘要
本文深入分析 LLVM 贪婪寄存器分配器（RAGreedy）的处理流程，详细描述从优先级队列获取虚拟寄存器、分配物理寄存器、处理分配失败的每一步逻辑。特别聚焦于驱逐、分割、溢出、重新着色和 CSR 处理的细粒度实现细节，包括数据结构交互、条件判断和优化策略。文档适合编译器开发者深入理解 RAGreedy 的内部机制。
目录
概述
RAGreedy 是 LLVM 代码生成流水线中的核心寄存器分配器，采用贪婪策略为虚拟寄存器分配物理寄存器，目标是最小化内存溢出并优化性能。其核心逻辑在 allocatePhysRegs 函数中，通过优先级队列（PriorityQueue）管理虚拟寄存器，并调用 selectOrSplit 分配物理寄存器。分配失败时，RAGreedy 使用驱逐、分割、溢出、重新着色和 CSR 处理等策略解决问题。本文将深入每个子步骤的处理逻辑，结合伪代码和数据结构交互细节。
处理流程
以下是 RAGreedy 的详细处理流程，分为五个主要阶段
1. 获取虚拟寄存器
RAGreedy 使用优先级队列管理虚拟寄存器（VirtReg），确保高优先级的寄存器优先分配。
1.1 优先级计算逻辑
优先级由 DefaultPriorityAdvisor::getPriority 计算，基于以下因素：
- 活跃区间大小：通过
LiveIntervals计算VirtReg的活跃区间长度（LiveInterval::getSize）。较大的区间优先级更高，因为溢出成本高。 - 寄存器类优先级：
TargetRegisterInfo定义寄存器类（如GPR、FPR）的优先级。例如，通用寄存器通常优先于专用寄存器。 - 全局 vs 局部：全局区间（跨多个基本块，
LiveInterval::isCrossBB）优先于局部区间（单基本块）。 - 分配提示：通过
getHints()获取提示寄存器（如拷贝指令r1 = COPY r2提示r1和r2使用同一寄存器），提示寄存器优先级更高。 - 分配阶段：
VirtReg的阶段（RS_Assign、RS_Split、RS_Spill）影响优先级。例如，RS_Assign（初始分配）优先于RS_Split（分割后）。
逻辑：
- 计算权重：
Weight = Size * Frequency + HintBonus，其中Frequency是基本块执行频率（MachineBlockFrequencyInfo），HintBonus是提示奖励。 - 比较权重：
getPriority返回比较值，优先级队列按降序排序。 - 命令行选项：
GreedyRegClassPriorityTrumpsGlobalness：优先寄存器类而非全局性。GreedyReverseLocalAssignment：优先短局部区间。
伪代码：
float getPriority(VirtReg) { LiveInterval &LI = LIS->getInterval(VirtReg); float Size = LI.getSize(); float Freq = MBFI->getBlockFreq(LI.getParentBB()); float HintBonus = hasHint(VirtReg) ? HINT_WEIGHT : 0; float Weight = Size * Freq + HintBonus; if (GreedyRegClassPriorityTrumpsGlobalness) Weight += RegClassPriority(LI.getRegClass()); if (GreedyReverseLocalAssignment && !LI.isCrossBB()) Weight = 1.0 / Weight; // 短区间优先 return Weight; } 1.2 队列操作
逻辑：
- 初始化：在
allocatePhysRegs中，遍历所有虚拟寄存器，调用enqueue加入队列：for (VirtReg in VirtRegMap) { Queue.enqueue(VirtReg, getPriority(VirtReg)); } - 获取：循环调用
dequeue获取最高优先级的VirtReg：while (Queue.hasReady()) { VirtReg = Queue.dequeue(); selectOrSplit(VirtReg, NewVRegs); } - 动态更新：新生成的虚拟寄存器（
NewVRegs）通过enqueue重新加入队列。
数据结构：
PriorityQueue：基于堆的优先级队列，维护VirtReg和优先级。LiveIntervals：存储活跃区间信息。MachineBlockFrequencyInfo：提供基本块频率。
结果：获取优先级最高的 VirtReg，传递给 selectOrSplit。
2. 分配物理寄存器
selectOrSplit 调用 selectOrSplitImpl 为 VirtReg 分配物理寄存器，返回 PhysReg 或 ~0u。
2.1 分配尝试逻辑
tryAssign 尝试分配物理寄存器，基于寄存器类和提示。
步骤：
- 初始化分配顺序：
- 使用
AllocationOrder生成物理寄存器列表：AllocationOrder Order(VirtReg, RegClass, TRI, Hints); - 顺序基于：
- 寄存器类约束（
RegClass）。 - 提示寄存器（
Hints）。 - 架构偏好（
TargetRegisterInfo::getAllocatableSet）。
- 寄存器类约束（
- 命令行选项
SplitThresholdForRegWithHint决定是否优先提示。
- 使用
- 遍历物理寄存器：
- 调用
Order.next()获取下一个PhysReg。
- 调用
- 冲突与分配：
- 调用
tryAssign检查PhysReg是否可用。
- 调用
伪代码：
unsigned tryAssign(LiveInterval &VirtReg, AllocationOrder &Order, SmallVectorImpl<unsigned> &NewVRegs) { while (unsigned PhysReg = Order.next()) { // 分配逻辑（见下文） } return ~0u; } 2.2 冲突检测与成本评估
逻辑：
- 冲突检测：
- 调用
LiveRegMatrix::checkInterference(VirtReg, PhysReg)：InterferenceKind IK = Matrix->checkInterference(VirtReg, PhysReg); - 返回值：
IK_Free：PhysReg空闲。IK_VirtReg：被其他虚拟寄存器占用。IK_PhysReg：被固定物理寄存器占用。
- 调用
- 成本评估：
- 计算
PhysReg成本（RegCosts）：float Cost = calculateRegCost(PhysReg, VirtReg); - 成本因素：
- 提示匹配：
isHint(VirtReg, PhysReg)降低成本。 - CSR 开销：
CSRCost（由CSRFirstTimeCost设置）。 - 别名成本：
TargetRegisterInfo::getAliasCost。
- 提示匹配：
- 判断：
- 若
Cost <= CostPerUseLimit，接受PhysReg。 - 否则，尝试驱逐。
- 若
- 计算
- 分配：
- 若
IK_Free且成本可接受：Matrix->assign(VirtReg, PhysReg); VRM->assignVirt2Phys(VirtReg, PhysReg); return PhysReg; - 若
IK_VirtReg，调用tryEvict。
- 若
伪代码：
unsigned tryAssign(LiveInterval &VirtReg, AllocationOrder &Order, SmallVectorImpl<unsigned> &NewVRegs) { while (unsigned PhysReg = Order.next()) { InterferenceKind IK = Matrix->checkInterference(VirtReg, PhysReg); if (IK == IK_Free) { if (isHint(VirtReg, PhysReg) || calculateRegCost(PhysReg) <= CostPerUseLimit) { Matrix->assign(VirtReg, PhysReg); VRM->assignVirt2Phys(VirtReg, PhysReg); return PhysReg; } } else if (IK == IK_VirtReg) { if (tryEvict(VirtReg, PhysReg, NewVRegs)) return PhysReg; } } if (!isHintAssigned(VirtReg)) SetOfBrokenHints.insert(VirtReg); return ~0u; } 数据结构：
LiveRegMatrix：管理干扰关系。VirtRegMap：记录虚拟到物理寄存器的映射。InterferenceCache：加速冲突检测。
结果：
- 成功：返回
PhysReg，更新状态。 - 失败：进入失败处理。
3. 处理分配失败
分配失败时，RAGreedy 按以下顺序尝试策略：
3.1 驱逐干扰
tryEvict 释放被占用的 PhysReg。
3.1.1 干扰识别
逻辑：
- 使用
LiveRegMatrix获取干扰寄存器：SmallVector<LiveInterval*, 8> Intfs; Matrix->getInterferences(VirtReg, PhysReg, Intfs);
3.1.2 驱逐候选选择
逻辑：
- 调用
EvictAdvisor::canEvictInterference：bool canEvict = EvictAdvisor->canEvictInterference(VirtReg, PhysReg); - 条件：
- 干扰寄存器可重新分配（
canReassign）。 - 驱逐成本低于
CostPerUseLimit：float EvictCost = calculateEvictCost(Intfs); if (EvictCost > CostPerUseLimit) return false;
- 干扰寄存器可重新分配（
- 优先选择低权重寄存器（
LiveInterval::getWeight）。
3.1.3 驱逐执行
逻辑：
- 调用
evictInterference：void evictInterference(LiveInterval &VirtReg, unsigned PhysReg, SmallVectorImpl<unsigned> &NewVRegs) { for (LiveInterval *Intf : Intfs) { Matrix->unassign(Intf); VRM->clearVirt(Intf->reg); NewVRegs.push_back(Intf->reg); } ++NumEvictions; } - 使用级联号防止循环驱逐：
VirtReg.Cascade++;
伪代码：
bool tryEvict(LiveInterval &VirtReg, unsigned PhysReg, SmallVectorImpl<unsigned> &NewVRegs) { SmallVector<LiveInterval*, 8> Intfs; Matrix->getInterferences(VirtReg, PhysReg, Intfs); if (!EvictAdvisor->canEvictInterference(VirtReg, PhysReg, Intfs)) return false; for (LiveInterval *Intf : Intfs) { Matrix->unassign(Intf); VRM->clearVirt(Intf->reg); NewVRegs.push_back(Intf->reg); } VirtReg.Cascade++; ++NumEvictions; return true; } 结果：
- 成功：返回
PhysReg。 - 失败：尝试分割。
3.2 分割活跃区间
trySplit 分割 VirtReg 的活跃区间，生成子区间。
3.2.1 局部分割
逻辑：
- 适用：单基本块内的活跃区间。
- 计算间隙权重（
calcGapWeights）：SmallVector<float, 16> GapWeights; calcGapWeights(VirtReg, GapWeights); - 选择最低成本的间隙：
unsigned BestGap = findMinWeightGap(GapWeights); - 分割：
LiveInterval *NewLI = splitLiveInterval(VirtReg, BestGap); NewVRegs.push_back(NewLI->reg);
3.2.2 区域分割
逻辑：
- 适用：跨块的全局区间。
- 使用
SpillPlacement分析活跃性：SpillPlacement->analyze(VirtReg); - 计算分割成本（
calculateRegionSplitCost）：float SplitCost = calculateRegionSplitCost(VirtReg, ColdRegions); if (SplitCost >= SpillCost) return false; - 在冷区域分割：
LiveInterval *NewLI = doRegionSplit(VirtReg, ColdRegions); NewVRegs.push_back(NewLI->reg);
3.2.3 块级分割
逻辑：
- 隔离到每个基本块：
SmallVector<LiveInterval*, 4> NewLIs; splitLiveIntervalPerBlock(VirtReg, NewLIs); for (LiveInterval *LI : NewLIs) NewVRegs.push_back(LI->reg);
3.2.4 指令级分割
逻辑：
- 围绕指令分割，优化受限寄存器类：
LiveInterval *NewLI = splitAroundInstruction(VirtReg, Instr); NewVRegs.push_back(NewLI->reg);
综合逻辑：
- 按顺序尝试分割类型：
unsigned trySplit(LiveInterval &VirtReg, AllocationOrder &Order, SmallVectorImpl<unsigned> &NewVRegs) { if (tryLocalSplit(VirtReg, Order, NewVRegs)) return 0; if (tryRegionSplit(VirtReg, Order, NewVRegs)) return 0; if (tryBlockSplit(VirtReg, Order, NewVRegs)) return 0; if (tryInstructionSplit(VirtReg, Order, NewVRegs)) return 0; return ~0u; } - 控制复杂性：
GrowRegionComplexityBudget限制子区间数量。
结果：
- 成功：新寄存器加入
NewVRegs。 - 失败：尝试溢出。
3.3 溢出
spill 将 VirtReg 溢出到内存。
3.3.1 溢出条件
逻辑：
- 检查是否可溢出：
if (!VirtReg.isSpillable()) return ~0u;
3.3.2 延迟溢出
逻辑：
- 若启用
EnableDeferredSpilling：VirtReg.Stage = RS_Memory; return 0;
3.3.3 溢出执行
逻辑：
- 使用
SpillerInstance：SpillerInstance->spill(&VirtReg, NewVRegs); - 生成加载/存储指令，更新
LiveIntervals和LiveDebugVariables。 - 标记
RS_Done。
伪代码：
unsigned spill(LiveInterval &VirtReg, SmallVectorImpl<unsigned> &NewVRegs) { if (!VirtReg.isSpillable()) return ~0u; if (EnableDeferredSpilling) { VirtReg.Stage = RS_Memory; return 0; } SpillerInstance->spill(&VirtReg, NewVRegs); VirtReg.Stage = RS_Done; ++NumSpills; return 0; } 结果：
- 成功：新寄存器加入队列。
- 失败：尝试重新着色。
3.4 最后机会重新着色
tryLastChanceRecoloring 重新分配干扰寄存器。
3.4.1 递归搜索
逻辑：
- 调用
tryRecoloringCandidates：bool tryRecoloringCandidates(LiveInterval &VirtReg, AllocationOrder &Order, SmallVectorImpl<unsigned> &NewVRegs); - 递归尝试为干扰寄存器分配新
PhysReg。
3.4.2 限制条件
逻辑：
- 最大深度：
LastChanceRecoloringMaxDepth。 - 最大干扰数量：
LastChanceRecoloringMaxInterference。 - 若
ExhaustiveSearch，禁用限制。
3.4.3 状态管理
逻辑：
FixedRegisters：防止重复着色。RecolorStack：记录状态，支持回滚。
伪代码：
unsigned tryLastChanceRecoloring(LiveInterval &VirtReg, AllocationOrder &Order, SmallVectorImpl<unsigned> &NewVRegs) { if (RecolorStack.size() >= LastChanceRecoloringMaxDepth && !ExhaustiveSearch) return ~0u; RecolorStack.push(VirtReg); if (tryRecoloringCandidates(VirtReg, Order, NewVRegs)) { PhysReg = Order.getLast(); Matrix->assign(VirtReg, PhysReg); VRM->assignVirt2Phys(VirtReg, PhysReg); RecolorStack.pop(); return PhysReg; } RecolorStack.pop(); return ~0u; } 结果：
- 成功：返回
PhysReg。 - 失败：触发错误。
3.5 CSR 处理
tryAssignCSRFirstTime 使用未用的 CSR。
3.5.1 成本比较
逻辑：
- 计算 CSR 成本：
float CSRCost = getCSRCost(VirtReg); - 比较：
if (CSRCost >= SpillCost || CSRCost >= SplitCost) return ~0u;
3.5.2 CSR 分配
逻辑：
- 分配 CSR：
PhysReg = Order.getCSR(); Matrix->assign(VirtReg, PhysReg); VRM->assignVirt2Phys(VirtReg, PhysReg); CostPerUseLimit = 1; // 限制后续驱逐
伪代码：
unsigned tryAssignCSRFirstTime(LiveInterval &VirtReg, AllocationOrder &Order, SmallVectorImpl<unsigned> &NewVRegs) { float CSRCost = getCSRCost(VirtReg); if (CSRCost < SpillCost && CSRCost < SplitCost) { unsigned PhysReg = Order.getCSR(); Matrix->assign(VirtReg, PhysReg); VRM->assignVirt2Phys(VirtReg, PhysReg); CostPerUseLimit = 1; return PhysReg; } return ~0u; } 4. 提示优化
tryHintsRecoloring 修复未分配到提示寄存器的 VirtReg。
4.1 拷贝分析
逻辑：
- 遍历
SetOfBrokenHints：for (unsigned VirtReg : SetOfBrokenHints) { collectHintInfo(VirtReg, Copies); } - 收集拷贝指令（如
r1 = COPY r2）。
4.2 重新着色优化
逻辑：
- 计算成本：
float Cost = getBrokenHintFreq(Copies); - 若重新着色降低成本：
tryHintRecoloring(VirtReg);
伪代码：
void tryHintsRecoloring() { for (unsigned VirtReg : SetOfBrokenHints) { SmallVector<MachineInstr*, 8> Copies; collectHintInfo(VirtReg, Copies); if (getBrokenHintFreq(Copies) > 0) { tryHintRecoloring(VirtReg); ++NumHintRecolorings; } } } 5. 后处理与统计
5.1 后处理
逻辑：
- 删除冗余拷贝：
removeRedundantCopies(); - 处理溢出/重载指令。
- 更新调试信息：
LiveDebugVariables->update();
5.2 统计报告
逻辑：
- 记录统计：
++NumSpills; ++NumReloads; ++NumCopies; - 生成报告：
MachineOptimizationRemarkMissed Report; Report.addStatistic("Spills", NumSpills);
5.3 资源释放
逻辑：
- 释放临时数据：
SpillerInstance.reset(); GlobalCand.clear();
总结
RAGreedy 通过优先级队列驱动的贪婪分配，结合细粒度的驱逐、分割、溢出和重新着色策略，实现高效寄存器分配。
![洛谷 P11345 [KTSC 2023 R2] 基地简化 题解](http://www.itfaba.com/wp-content/themes/kemi/timthumb.php?src=http://www.itfaba.com/wp-content/themes/kemi/img/random/1.jpg&w=218&h=124&zc=1)
