在LLVM中的greedy Register Allocation pass代码详解
LLVM 贪婪寄存器分配器（RAGreedy）详细处理流程日期: 2025年5月29日
摘要
本文深入分析 LLVM 贪婪寄存器分配器（RAGreedy）的处理流程，详细描述从优先级队列获取虚拟寄存器、分配物理寄存器、处理分配失败的每一步逻辑。特别聚焦于驱逐、分割、溢出、重新着色和 CSR 处理的细粒度实现细节，包括数据结构交互、条件判断和优化策略。文档适合编译器开发者深入理解 RAGreedy 的内部机制。
目录
[*]概述
[*]处理流程
[*]1. 获取虚拟寄存器
[*]1.1 优先级计算逻辑
[*]1.2 队列操作
[*]2. 分配物理寄存器
[*]2.1 分配尝试逻辑
[*]2.2 冲突检测与成本评估
[*]3. 处理分配失败
[*]3.1 驱逐干扰
[*]3.1.1 干扰识别
[*]3.1.2 驱逐候选选择
[*]3.1.3 驱逐执行
[*]3.2 分割活跃区间
[*]3.2.1 局部分割
[*]3.2.2 区域分割
[*]3.2.3 块级分割
[*]3.2.4 指令级分割
[*]3.3 溢出
[*]3.3.1 溢出条件
[*]3.3.2 延迟溢出
[*]3.3.3 溢出执行
[*]3.4 最后机会重新着色
[*]3.4.1 递归搜索
[*]3.4.2 限制条件
[*]3.4.3 状态管理
[*]3.5 CSR 处理
[*]3.5.1 成本比较
[*]3.5.2 CSR 分配
[*]4. 提示优化
[*]4.1 拷贝分析
[*]4.2 重新着色优化
[*]5. 后处理与统计
[*]5.1 后处理
[*]5.2 统计报告
[*]5.3 资源释放
[*]关键优化点
[*]调试与分析
[*]总结
概述
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 冲突检测与成本评估
逻辑：
<ul>冲突检测：
[*]调用 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 assign(VirtReg, PhysReg);VRM->assignVirt2Phys(VirtReg, PhysReg);return PhysReg;
[*]若 IK_VirtReg，调用 tryEvict。
伪代码：
Matrix->assign(VirtReg, PhysReg);
VRM->assignVirt2Phys(VirtReg, PhysReg);
return PhysReg;数据结构：
[*]LiveRegMatrix：管理干扰关系。
[*]VirtRegMap：记录虚拟到物理寄存器的映射。
[*]InterferenceCache：加速冲突检测。
结果：
[*]成功：返回 PhysReg，更新状态。
[*]失败：进入失败处理。
3. 处理分配失败
分配失败时，RAGreedy 按以下顺序尝试策略：
3.1 驱逐干扰
tryEvict 释放被占用的 PhysReg。
3.1.1 干扰识别
逻辑：
[*]使用 LiveRegMatrix 获取干扰寄存器：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;
}
3.1.2 驱逐候选选择
逻辑：
[*]调用 EvictAdvisor::canEvictInterference：SmallVector<LiveInterval*, 8> Intfs;
Matrix->getInterferences(VirtReg, PhysReg, Intfs);
[*]条件：
[*]干扰寄存器可重新分配（canReassign）。
[*]驱逐成本低于 CostPerUseLimit：bool canEvict = EvictAdvisor->canEvictInterference(VirtReg, PhysReg);
[*]优先选择低权重寄存器（LiveInterval::getWeight）。
3.1.3 驱逐执行
逻辑：
[*]调用 evictInterference：float EvictCost = calculateEvictCost(Intfs);
if (EvictCost > CostPerUseLimit) return false;
[*]使用级联号防止循环驱逐：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;
}
伪代码：
bool tryEvict(LiveInterval &VirtReg, unsigned PhysReg, SmallVectorImpl &NewVRegs) {SmallVector 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);}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;
}++NumEvictions;return true;}结果：
[*]成功：返回 PhysReg。
[*]失败：尝试分割。
3.2 分割活跃区间
trySplit 分割 VirtReg 的活跃区间，生成子区间。
3.2.1 局部分割
逻辑：
[*]适用：单基本块内的活跃区间。
[*]计算间隙权重（calcGapWeights）：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;
}
[*]选择最低成本的间隙：SmallVector<float, 16> GapWeights;
calcGapWeights(VirtReg, GapWeights);
[*]分割：unsigned BestGap = findMinWeightGap(GapWeights);
3.2.2 区域分割
逻辑：
[*]适用：跨块的全局区间。
[*]使用 SpillPlacement 分析活跃性：LiveInterval *NewLI = splitLiveInterval(VirtReg, BestGap);
NewVRegs.push_back(NewLI->reg);
[*]计算分割成本（calculateRegionSplitCost）：SpillPlacement->analyze(VirtReg);
[*]在冷区域分割：float SplitCost = calculateRegionSplitCost(VirtReg, ColdRegions);
if (SplitCost >= SpillCost) return false;
3.2.3 块级分割
逻辑：
[*]隔离到每个基本块：LiveInterval *NewLI = doRegionSplit(VirtReg, ColdRegions);
NewVRegs.push_back(NewLI->reg);
3.2.4 指令级分割
逻辑：
[*]围绕指令分割，优化受限寄存器类：SmallVector<LiveInterval*, 4> NewLIs;
splitLiveIntervalPerBlock(VirtReg, NewLIs);
for (LiveInterval *LI : NewLIs)
NewVRegs.push_back(LI->reg);
综合逻辑：
[*]按顺序尝试分割类型：LiveInterval *NewLI = splitAroundInstruction(VirtReg, Instr);
NewVRegs.push_back(NewLI->reg);
[*]控制复杂性：GrowRegionComplexityBudget 限制子区间数量。
结果：
[*]成功：新寄存器加入 NewVRegs。
[*]失败：尝试溢出。
3.3 溢出
spill 将 VirtReg 溢出到内存。
3.3.1 溢出条件
逻辑：
[*]检查是否可溢出：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;
}
3.3.2 延迟溢出
逻辑：
[*]若启用 EnableDeferredSpilling：if (!VirtReg.isSpillable()) return ~0u;
3.3.3 溢出执行
逻辑：
[*]使用 SpillerInstance：VirtReg.Stage = RS_Memory;
return 0;
[*]生成加载/存储指令，更新 LiveIntervals 和 LiveDebugVariables。
[*]标记 RS_Done。
伪代码：
unsigned spill(LiveInterval &VirtReg, SmallVectorImpl &NewVRegs) {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;
}if (EnableDeferredSpilling) { VirtReg.Stage = RS_Memory; return 0;}VirtReg.Stage = RS_Memory;
return 0;VirtReg.Stage = RS_Done;++NumSpills;return 0;}结果：
[*]成功：新寄存器加入队列。
[*]失败：尝试重新着色。
3.4 最后机会重新着色
tryLastChanceRecoloring 重新分配干扰寄存器。
3.4.1 递归搜索
逻辑：
[*]调用 tryRecoloringCandidates：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;
}
[*]递归尝试为干扰寄存器分配新 PhysReg。
3.4.2 限制条件
逻辑：
[*]最大深度：LastChanceRecoloringMaxDepth。
[*]最大干扰数量：LastChanceRecoloringMaxInterference。
[*]若 ExhaustiveSearch，禁用限制。
3.4.3 状态管理
逻辑：
[*]FixedRegisters：防止重复着色。
[*]RecolorStack：记录状态，支持回滚。
伪代码：
bool tryRecoloringCandidates(LiveInterval &VirtReg, AllocationOrder &Order, SmallVectorImpl<unsigned> &NewVRegs);结果：
[*]成功：返回 PhysReg。
[*]失败：触发错误。
3.5 CSR 处理
tryAssignCSRFirstTime 使用未用的 CSR。
3.5.1 成本比较
逻辑：
[*]计算 CSR 成本：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;
}
[*]比较：float CSRCost = getCSRCost(VirtReg);
3.5.2 CSR 分配
逻辑：
[*]分配 CSR：if (CSRCost >= SpillCost || CSRCost >= SplitCost) return ~0u;
伪代码：
unsigned tryAssignCSRFirstTime(LiveInterval &VirtReg, AllocationOrder &Order, SmallVectorImpl &NewVRegs) {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;
}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：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;
}
[*]收集拷贝指令（如 r1 = COPY r2）。
4.2 重新着色优化
逻辑：
[*]计算成本：for (unsigned VirtReg : SetOfBrokenHints) {
collectHintInfo(VirtReg, Copies);
}
[*]若重新着色降低成本：float Cost = getBrokenHintFreq(Copies);
伪代码：
void tryHintsRecoloring() {for (unsigned VirtReg : SetOfBrokenHints) { SmallVector Copies; collectHintInfo(VirtReg, Copies); if (getBrokenHintFreq(Copies) > 0) { float Cost = getBrokenHintFreq(Copies); ++NumHintRecolorings; }}}5. 后处理与统计
5.1 后处理
逻辑：
[*]删除冗余拷贝：void tryHintsRecoloring() {
for (unsigned VirtReg : SetOfBrokenHints) {
SmallVector<MachineInstr*, 8> Copies;
collectHintInfo(VirtReg, Copies);
if (getBrokenHintFreq(Copies) > 0) {
tryHintRecoloring(VirtReg);
++NumHintRecolorings;
}
}
}
[*]处理溢出/重载指令。
[*]更新调试信息：removeRedundantCopies();
5.2 统计报告
逻辑：
[*]记录统计：LiveDebugVariables->update();
[*]生成报告：++NumSpills; ++NumReloads; ++NumCopies;
5.3 资源释放
逻辑：
[*]释放临时数据：MachineOptimizationRemarkMissed Report;
Report.addStatistic("Spills", NumSpills);
总结
RAGreedy 通过优先级队列驱动的贪婪分配，结合细粒度的驱逐、分割、溢出和重新着色策略，实现高效寄存器分配。
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ 谢谢分享，辛苦了 谢谢分享，辛苦了 鼓励转贴优秀软件安全工具和文档！
页:
[1]