登录/ 注册
 找回密码
 立即注册
关闭

CSDN热搜

程序园 精品问答 技术交流 资源下载
返回列表 发新帖
首页 › 业界区 › 业界 ›在LLVM中的greedy Register Allocation pass代码详解 ...

在LLVM中的greedy Register Allocation pass代码详解

廖雯华 前天 10:27
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：优先短局部区间。

伪代码：
  1. float getPriority(VirtReg) {
  2.   LiveInterval &LI = LIS->getInterval(VirtReg);
  3.   float Size = LI.getSize();
  4.   float Freq = MBFI->getBlockFreq(LI.getParentBB());
  5.   float HintBonus = hasHint(VirtReg) ? HINT_WEIGHT : 0;
  6.   float Weight = Size * Freq + HintBonus;
  7.   if (GreedyRegClassPriorityTrumpsGlobalness)
  8.     Weight += RegClassPriority(LI.getRegClass());
  9.   if (GreedyReverseLocalAssignment && !LI.isCrossBB())
  10.     Weight = 1.0 / Weight; // 短区间优先
  11.   return Weight;
  12. }
复制代码
1.2 队列操作

逻辑：

  • 初始化：在 allocatePhysRegs 中，遍历所有虚拟寄存器，调用 enqueue 加入队列：
    1. for (VirtReg in VirtRegMap) {
    2.   Queue.enqueue(VirtReg, getPriority(VirtReg));
    3. }
    复制代码
  • 获取：循环调用 dequeue 获取最高优先级的 VirtReg：
    1. while (Queue.hasReady()) {
    2.   VirtReg = Queue.dequeue();
    3.   selectOrSplit(VirtReg, NewVRegs);
    4. }
    复制代码
  • 动态更新：新生成的虚拟寄存器（NewVRegs）通过 enqueue 重新加入队列。
数据结构：

  • PriorityQueue：基于堆的优先级队列，维护 VirtReg 和优先级。
  • LiveIntervals：存储活跃区间信息。
  • MachineBlockFrequencyInfo：提供基本块频率。
结果：获取优先级最高的 VirtReg，传递给 selectOrSplit。
2. 分配物理寄存器

selectOrSplit 调用 selectOrSplitImpl 为 VirtReg 分配物理寄存器，返回 PhysReg 或 ~0u。
2.1 分配尝试逻辑

tryAssign 尝试分配物理寄存器，基于寄存器类和提示。
步骤：

  • 初始化分配顺序：

    • 使用 AllocationOrder 生成物理寄存器列表：
      1. AllocationOrder Order(VirtReg, RegClass, TRI, Hints);
      复制代码
    • 顺序基于：

      • 寄存器类约束（RegClass）。
      • 提示寄存器（Hints）。
      • 架构偏好（TargetRegisterInfo::getAllocatableSet）。

    • 命令行选项 SplitThresholdForRegWithHint 决定是否优先提示。

  • 遍历物理寄存器：

    • 调用 Order.next() 获取下一个 PhysReg。

  • 冲突与分配：

    • 调用 tryAssign 检查 PhysReg 是否可用。

伪代码：
  1. unsigned tryAssign(LiveInterval &VirtReg, AllocationOrder &Order, SmallVectorImpl<unsigned> &NewVRegs) {
  2.   while (unsigned PhysReg = Order.next()) {
  3.     // 分配逻辑（见下文）
  4.   }
  5.   return ~0u;
  6. }
复制代码
2.2 冲突检测与成本评估

逻辑：
<ul>冲突检测：

  • 调用 LiveRegMatrix::checkInterference(VirtReg, PhysReg)：
    1. InterferenceKind IK = Matrix->checkInterference(VirtReg, PhysReg);
    复制代码
  • 返回值：

    • IK_Free：PhysReg 空闲。
    • IK_VirtReg：被其他虚拟寄存器占用。
    • IK_PhysReg：被固定物理寄存器占用。

成本评估：

  • 计算 PhysReg 成本（RegCosts）：
    1. float Cost = calculateRegCost(PhysReg, VirtReg);
    复制代码
  • 成本因素：

    • 提示匹配：isHint(VirtReg, PhysReg) 降低成本。
    • CSR 开销：CSRCost（由 CSRFirstTimeCost 设置）。
    • 别名成本：TargetRegisterInfo::getAliasCost。

  • 判断：

    • 若 Cost assign(VirtReg, PhysReg);VRM->assignVirt2Phys(VirtReg, PhysReg);return PhysReg;[/code]
    • 若 IK_VirtReg，调用 tryEvict。

伪代码：
  1. Matrix->assign(VirtReg, PhysReg);
  2. VRM->assignVirt2Phys(VirtReg, PhysReg);
  3. return PhysReg;
复制代码
数据结构：

  • LiveRegMatrix：管理干扰关系。
  • VirtRegMap：记录虚拟到物理寄存器的映射。
  • InterferenceCache：加速冲突检测。
结果：

  • 成功：返回 PhysReg，更新状态。
  • 失败：进入失败处理。
3. 处理分配失败

分配失败时，RAGreedy 按以下顺序尝试策略：
3.1 驱逐干扰

tryEvict 释放被占用的 PhysReg。
3.1.1 干扰识别

逻辑：

  • 使用 LiveRegMatrix 获取干扰寄存器：
    1. unsigned tryAssign(LiveInterval &VirtReg, AllocationOrder &Order, SmallVectorImpl<unsigned> &NewVRegs) {
    2.   while (unsigned PhysReg = Order.next()) {
    3.     InterferenceKind IK = Matrix->checkInterference(VirtReg, PhysReg);
    4.     if (IK == IK_Free) {
    5.       if (isHint(VirtReg, PhysReg) || calculateRegCost(PhysReg) <= CostPerUseLimit) {
    6.         Matrix->assign(VirtReg, PhysReg);
    7.         VRM->assignVirt2Phys(VirtReg, PhysReg);
    8.         return PhysReg;
    9.       }
    10.     } else if (IK == IK_VirtReg) {
    11.       if (tryEvict(VirtReg, PhysReg, NewVRegs))
    12.         return PhysReg;
    13.     }
    14.   }
    15.   if (!isHintAssigned(VirtReg))
    16.     SetOfBrokenHints.insert(VirtReg);
    17.   return ~0u;
    18. }
    复制代码
3.1.2 驱逐候选选择

逻辑：

  • 调用 EvictAdvisor::canEvictInterference：
    1. SmallVector<LiveInterval*, 8> Intfs;
    2. Matrix->getInterferences(VirtReg, PhysReg, Intfs);
    复制代码
  • 条件：

    • 干扰寄存器可重新分配（canReassign）。
    • 驱逐成本低于 CostPerUseLimit：
      1. bool canEvict = EvictAdvisor->canEvictInterference(VirtReg, PhysReg);
      复制代码

  • 优先选择低权重寄存器（LiveInterval::getWeight）。
3.1.3 驱逐执行

逻辑：

  • 调用 evictInterference：
    1. float EvictCost = calculateEvictCost(Intfs);
    2. if (EvictCost > CostPerUseLimit) return false;
    复制代码
  • 使用级联号防止循环驱逐：
    1. void evictInterference(LiveInterval &VirtReg, unsigned PhysReg, SmallVectorImpl<unsigned> &NewVRegs) {
    2.   for (LiveInterval *Intf : Intfs) {
    3.     Matrix->unassign(Intf);
    4.     VRM->clearVirt(Intf->reg);
    5.     NewVRegs.push_back(Intf->reg);
    6.   }
    7.   ++NumEvictions;
    8. }
    复制代码
伪代码：
  1. 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) {
  2.   for (LiveInterval *Intf : Intfs) {
  3.     Matrix->unassign(Intf);
  4.     VRM->clearVirt(Intf->reg);
  5.     NewVRegs.push_back(Intf->reg);
  6.   }
  7.   ++NumEvictions;
  8. }  ++NumEvictions;  return true;}
复制代码
结果：

  • 成功：返回 PhysReg。
  • 失败：尝试分割。
3.2 分割活跃区间

trySplit 分割 VirtReg 的活跃区间，生成子区间。
3.2.1 局部分割

逻辑：

  • 适用：单基本块内的活跃区间。
  • 计算间隙权重（calcGapWeights）：
    1. bool tryEvict(LiveInterval &VirtReg, unsigned PhysReg, SmallVectorImpl<unsigned> &NewVRegs) {
    2.   SmallVector<LiveInterval*, 8> Intfs;
    3.   Matrix->getInterferences(VirtReg, PhysReg, Intfs);
    4.   if (!EvictAdvisor->canEvictInterference(VirtReg, PhysReg, Intfs))
    5.     return false;
    6.   for (LiveInterval *Intf : Intfs) {
    7.     Matrix->unassign(Intf);
    8.     VRM->clearVirt(Intf->reg);
    9.     NewVRegs.push_back(Intf->reg);
    10.   }
    11.   VirtReg.Cascade++;
    12.   ++NumEvictions;
    13.   return true;
    14. }
    复制代码
  • 选择最低成本的间隙：
    1. SmallVector<float, 16> GapWeights;
    2. calcGapWeights(VirtReg, GapWeights);
    复制代码
  • 分割：
    1. unsigned BestGap = findMinWeightGap(GapWeights);
    复制代码
3.2.2 区域分割

逻辑：

  • 适用：跨块的全局区间。
  • 使用 SpillPlacement 分析活跃性：
    1. LiveInterval *NewLI = splitLiveInterval(VirtReg, BestGap);
    2. NewVRegs.push_back(NewLI->reg);
    复制代码
  • 计算分割成本（calculateRegionSplitCost）：
    1. SpillPlacement->analyze(VirtReg);
    复制代码
  • 在冷区域分割：
    1. float SplitCost = calculateRegionSplitCost(VirtReg, ColdRegions);
    2. if (SplitCost >= SpillCost) return false;
    复制代码
3.2.3 块级分割

逻辑：

  • 隔离到每个基本块：
    1. LiveInterval *NewLI = doRegionSplit(VirtReg, ColdRegions);
    2. NewVRegs.push_back(NewLI->reg);
    复制代码
3.2.4 指令级分割

逻辑：

  • 围绕指令分割，优化受限寄存器类：
    1. SmallVector<LiveInterval*, 4> NewLIs;
    2. splitLiveIntervalPerBlock(VirtReg, NewLIs);
    3. for (LiveInterval *LI : NewLIs)
    4.   NewVRegs.push_back(LI->reg);
    复制代码
综合逻辑：

  • 按顺序尝试分割类型：
    1. LiveInterval *NewLI = splitAroundInstruction(VirtReg, Instr);
    2. NewVRegs.push_back(NewLI->reg);
    复制代码
  • 控制复杂性：GrowRegionComplexityBudget 限制子区间数量。
结果：

  • 成功：新寄存器加入 NewVRegs。
  • 失败：尝试溢出。
3.3 溢出

spill 将 VirtReg 溢出到内存。
3.3.1 溢出条件

逻辑：

  • 检查是否可溢出：
    1. unsigned trySplit(LiveInterval &VirtReg, AllocationOrder &Order, SmallVectorImpl<unsigned> &NewVRegs) {
    2.   if (tryLocalSplit(VirtReg, Order, NewVRegs)) return 0;
    3.   if (tryRegionSplit(VirtReg, Order, NewVRegs)) return 0;
    4.   if (tryBlockSplit(VirtReg, Order, NewVRegs)) return 0;
    5.   if (tryInstructionSplit(VirtReg, Order, NewVRegs)) return 0;
    6.   return ~0u;
    7. }
    复制代码
3.3.2 延迟溢出

逻辑：

  • 若启用 EnableDeferredSpilling：
    1. if (!VirtReg.isSpillable()) return ~0u;
    复制代码
3.3.3 溢出执行

逻辑：

  • 使用 SpillerInstance：
    1. VirtReg.Stage = RS_Memory;
    2. return 0;
    复制代码
  • 生成加载/存储指令，更新 LiveIntervals 和 LiveDebugVariables。
  • 标记 RS_Done。
伪代码：
  1. unsigned spill(LiveInterval &VirtReg, SmallVectorImpl &NewVRegs) {  unsigned trySplit(LiveInterval &VirtReg, AllocationOrder &Order, SmallVectorImpl<unsigned> &NewVRegs) {
  2.   if (tryLocalSplit(VirtReg, Order, NewVRegs)) return 0;
  3.   if (tryRegionSplit(VirtReg, Order, NewVRegs)) return 0;
  4.   if (tryBlockSplit(VirtReg, Order, NewVRegs)) return 0;
  5.   if (tryInstructionSplit(VirtReg, Order, NewVRegs)) return 0;
  6.   return ~0u;
  7. }  if (EnableDeferredSpilling) {    VirtReg.Stage = RS_Memory;    return 0;  }  VirtReg.Stage = RS_Memory;
  8. return 0;  VirtReg.Stage = RS_Done;  ++NumSpills;  return 0;}
复制代码
结果：

  • 成功：新寄存器加入队列。
  • 失败：尝试重新着色。
3.4 最后机会重新着色

tryLastChanceRecoloring 重新分配干扰寄存器。
3.4.1 递归搜索

逻辑：

  • 调用 tryRecoloringCandidates：
    1. unsigned spill(LiveInterval &VirtReg, SmallVectorImpl<unsigned> &NewVRegs) {
    2.   if (!VirtReg.isSpillable()) return ~0u;
    3.   if (EnableDeferredSpilling) {
    4.     VirtReg.Stage = RS_Memory;
    5.     return 0;
    6.   }
    7.   SpillerInstance->spill(&VirtReg, NewVRegs);
    8.   VirtReg.Stage = RS_Done;
    9.   ++NumSpills;
    10.   return 0;
    11. }
    复制代码
  • 递归尝试为干扰寄存器分配新 PhysReg。
3.4.2 限制条件

逻辑：

  • 最大深度：LastChanceRecoloringMaxDepth。
  • 最大干扰数量：LastChanceRecoloringMaxInterference。
  • 若 ExhaustiveSearch，禁用限制。
3.4.3 状态管理

逻辑：

  • FixedRegisters：防止重复着色。
  • RecolorStack：记录状态，支持回滚。
伪代码：
  1. bool tryRecoloringCandidates(LiveInterval &VirtReg, AllocationOrder &Order, SmallVectorImpl<unsigned> &NewVRegs);
复制代码
结果：

  • 成功：返回 PhysReg。
  • 失败：触发错误。
3.5 CSR 处理

tryAssignCSRFirstTime 使用未用的 CSR。
3.5.1 成本比较

逻辑：

  • 计算 CSR 成本：
    1. unsigned tryLastChanceRecoloring(LiveInterval &VirtReg, AllocationOrder &Order, SmallVectorImpl<unsigned> &NewVRegs) {
    2.   if (RecolorStack.size() >= LastChanceRecoloringMaxDepth && !ExhaustiveSearch)
    3.     return ~0u;
    4.   RecolorStack.push(VirtReg);
    5.   if (tryRecoloringCandidates(VirtReg, Order, NewVRegs)) {
    6.     PhysReg = Order.getLast();
    7.     Matrix->assign(VirtReg, PhysReg);
    8.     VRM->assignVirt2Phys(VirtReg, PhysReg);
    9.     RecolorStack.pop();
    10.     return PhysReg;
    11.   }
    12.   RecolorStack.pop();
    13.   return ~0u;
    14. }
    复制代码
  • 比较：
    1. float CSRCost = getCSRCost(VirtReg);
    复制代码
3.5.2 CSR 分配

逻辑：

  • 分配 CSR：
    1. if (CSRCost >= SpillCost || CSRCost >= SplitCost) return ~0u;
    复制代码
伪代码：
  1. unsigned tryAssignCSRFirstTime(LiveInterval &VirtReg, AllocationOrder &Order, SmallVectorImpl &NewVRegs) {  unsigned tryLastChanceRecoloring(LiveInterval &VirtReg, AllocationOrder &Order, SmallVectorImpl<unsigned> &NewVRegs) {
  2.   if (RecolorStack.size() >= LastChanceRecoloringMaxDepth && !ExhaustiveSearch)
  3.     return ~0u;
  4.   RecolorStack.push(VirtReg);
  5.   if (tryRecoloringCandidates(VirtReg, Order, NewVRegs)) {
  6.     PhysReg = Order.getLast();
  7.     Matrix->assign(VirtReg, PhysReg);
  8.     VRM->assignVirt2Phys(VirtReg, PhysReg);
  9.     RecolorStack.pop();
  10.     return PhysReg;
  11.   }
  12.   RecolorStack.pop();
  13.   return ~0u;
  14. }  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：
    1. unsigned tryAssignCSRFirstTime(LiveInterval &VirtReg, AllocationOrder &Order, SmallVectorImpl<unsigned> &NewVRegs) {
    2.   float CSRCost = getCSRCost(VirtReg);
    3.   if (CSRCost < SpillCost && CSRCost < SplitCost) {
    4.     unsigned PhysReg = Order.getCSR();
    5.     Matrix->assign(VirtReg, PhysReg);
    6.     VRM->assignVirt2Phys(VirtReg, PhysReg);
    7.     CostPerUseLimit = 1;
    8.     return PhysReg;
    9.   }
    10.   return ~0u;
    11. }
    复制代码
  • 收集拷贝指令（如 r1 = COPY r2）。
4.2 重新着色优化

逻辑：

  • 计算成本：
    1. for (unsigned VirtReg : SetOfBrokenHints) {
    2.   collectHintInfo(VirtReg, Copies);
    3. }
    复制代码
  • 若重新着色降低成本：
    1. float Cost = getBrokenHintFreq(Copies);
    复制代码
伪代码：
  1. void tryHintsRecoloring() {  for (unsigned VirtReg : SetOfBrokenHints) {    SmallVector Copies;    collectHintInfo(VirtReg, Copies);    if (getBrokenHintFreq(Copies) > 0) {      float Cost = getBrokenHintFreq(Copies);      ++NumHintRecolorings;    }  }}
复制代码
5. 后处理与统计

5.1 后处理

逻辑：

  • 删除冗余拷贝：
    1. void tryHintsRecoloring() {
    2.   for (unsigned VirtReg : SetOfBrokenHints) {
    3.     SmallVector<MachineInstr*, 8> Copies;
    4.     collectHintInfo(VirtReg, Copies);
    5.     if (getBrokenHintFreq(Copies) > 0) {
    6.       tryHintRecoloring(VirtReg);
    7.       ++NumHintRecolorings;
    8.     }
    9.   }
    10. }
    复制代码
  • 处理溢出/重载指令。
  • 更新调试信息：
    1. removeRedundantCopies();
    复制代码
5.2 统计报告

逻辑：

  • 记录统计：
    1. LiveDebugVariables->update();
    复制代码
  • 生成报告：
    1. ++NumSpills; ++NumReloads; ++NumCopies;
    复制代码
5.3 资源释放

逻辑：

  • 释放临时数据：
    1. MachineOptimizationRemarkMissed Report;
    2. Report.addStatistic("Spills", NumSpills);
    复制代码
总结

RAGreedy 通过优先级队列驱动的贪婪分配，结合细粒度的驱逐、分割、溢出和重新着色策略，实现高效寄存器分配。

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

使用道具 举报
相关推荐
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册
发帖
廖雯华
前天 10:27

0

粉丝关注

11

主题发布

板块介绍填写区域，请于后台编辑
微信扫一扫