InlineSpiller

这算是后端一个较为大型的 Pass 了，有 1700 多行。但是严格来说它只是一个辅助文件，隶属于寄存器分配模块。

这个 Pass 一看又是涉及了一大堆概念，它是 LLVM 寄存器分配阶段中的一个专门化 Spiller，它绕过 VirtRegMap 默认的 spill/restore 逻辑，直接在 MachineFunction 中插入 spill 和 reload 指令，以便后续的“内联”内存操作折叠（memory operand folding）和 spill 提升（hoisting）等优化能够生效。
如果没有深入研究过后端的话，不妨先看一下如下一些概念：

  1. 寄存器分配（Register Allocation）
    • 编译器后端要把“无限”的虚拟寄存器映射到“稀缺”的物理寄存器上。分配失败时，需要把某些值暂存到栈上（spill）再在用到时 reload 回来。
  2. LiveInterval / LiveRange
    • 描述某个虚拟寄存器在程序中存活（“活跃”）的区间。LiveIntervals 管理所有虚拟寄存器的活跃区间，用来指导寄存器分配和 spill。
  3. Spiller 与 spill/reload
    • Spiller 是一个抽象类，负责在寄存器不足时插入 spill（STORE 到栈）和 reload（LOAD 回寄存器）操作。InlineSpiller 就是它的子类，实现了“内联”式的 spill 策略。
  4. LiveRangeEdit
    • 用来对某条活跃区间做“切片”：把一个大的活跃区间拆成若干小段，在每段之间插入 spill/reload。spill(LiveRangeEdit&) 就是对单个虚拟寄存器区间进行这种切分和指令插入。
  5. Snippet（短活跃段）
    • 指只在一处被使用的短小活跃区间。InlineSpiller 会把这些 snippet 也 spill 到同一个栈槽，以便后续“内联折叠”能把它们合并。
  6. foldMemoryOperand（内存操作折叠）
    • 一些目标指令集支持直接在指令里访问栈槽（如 LOAD [sp+8], r0 形式）。折叠机制尝试把独立的 spill/reload 合并进相邻的算术／访存指令，减少额外指令。
  7. Spill Hoisting（spill 提升）
    • 如果同一个栈槽有多次连续的 spill，可以沿着控制流向上“提”到共同的支配者块（dominator），减少重复 spill。需要用到支配树（Dominator Tree）和块频率信息（Block Frequency Info）。
  8. VirtRegMap / VirtRegAuxInfo
    • VirtRegMap 管理虚拟寄存器到物理寄存器或栈槽的最终映射；
    • VirtRegAuxInfo 存储一些辅助信息，如哪些虚拟寄存器允许重物化（rematerialize）而不是 spill。
      下面再来举两个例子分别说明下什么是“内存操作折叠”和“Spill 提升”：
      ①折叠前：
;; 将 spill 到栈上的值 reload 回 rax
LOAD64spill  rax, [rsp+8]

;; 再进行加法
ADD64ri      rax, rax, 5

②折叠后：

;; 直接把“从 [rsp+8] 加 5”的操作折叠到一条指令里

ADD64ri_mem  rax, [rsp+8], 5

①提升前：

entry:
  ; … 初始化 …
  br %loop

loop:                   ; loop 是 entry 的后继块, 循环体会多次spill
  LOAD64spill  rbx, [rsp+16]   ; reload
  ; 使用 rbx
  STORE64spill rbx, [rsp+16]   ; spill
  br %loop

exit:
  ret

②提升后：

entry:
  ; 只在 loop 入口做一次 spill
  STORE64spill rbx, [rsp+16]
  br %loop

loop:
  LOAD64spill  rbx, [rsp+16]   ; reload
  ; 使用 rbx
  br %loop

exit:
  ret

现在就可以来看源码了。它的调试信息属于"regalloc"，可以获得如下统计信息：

STATISTIC(NumSpilledRanges,   "Number of spilled live ranges");  
STATISTIC(NumSnippets,        "Number of spilled snippets");  
STATISTIC(NumSpills,          "Number of spills inserted");  
STATISTIC(NumSpillsRemoved,   "Number of spills removed");  
STATISTIC(NumReloads,         "Number of reloads inserted");  
STATISTIC(NumReloadsRemoved,  "Number of reloads removed");  
STATISTIC(NumFolded,          "Number of folded stack accesses");  
STATISTIC(NumFoldedLoads,     "Number of folded loads");  
STATISTIC(NumRemats,          "Number of rematerialized defs for spilling");

这个文件主要围绕两个互补的组件展开：

1. HoistSpillHelper：跨块 Spill 提升工具
  • 职责：收集“相同栈槽、相同原始值” 的多处 spill 指令（MergeableSpills），然后沿着支配树把多余的 spill 向上“提”到共同的支配块，从而减少重复的内存写。
  • 关键数据结构
    • StackSlotToOrigLI：为每个栈槽保存一份原始寄存器的 LiveInterval 副本，方便计算哪些 spill 可以合并／提升。
    • MergeableSpillsMap：以 (StackSlot, VNInfo*) 为键，收集可合并的 spill 指令集合。
    • Virt2SiblingsMap：纪录“原始寄存器 → 它的所有拆分后子寄存器（siblings）”，用来判断在目标提升块里有没有仍然活跃的副本可供 spill。
  • 关键方法
    1. addToMergeableSpills(Spill, Slot, Original)
    每次插入真实 spill（storeRegToStackSlot）后调用，把这条 spill 归入合并候选集合。
    2. rmFromMergeableSpills(Spill, Slot)
    在后续 fold 或删除冗余时，把不再需要的 spill 从候选集中移除。
    3. hoistAllSpills()
    - 遍历 MergeableSpills 中的每一组等值 spill；
    - 调用内部的 runHoistSpills()：
    - 先用 rmRedundantSpills() 在同一基本块里留下最早的 spill；
    - 再借助支配树遍历（getVisitOrders()）和块频信息，在热度最优的支配块插入新的 spill，并把原来位置的 spill 标记为删除；
    - 最后实际插入新 spill、删除冗余 spill。
2. InlineSpiller：“内联”式 Spill/Reload Pass
  • 继承关系：
class InlineSpiller : public Spiller { … };
  • 注册时由 createInlineSpiller() 工厂函数插入到寄存器分配阶段。
  • 整体流程（spill(LiveRangeEdit &edit, AllocationOrder *order)）
    1. 确定要处理的虚拟寄存器：
      • Original = VRM.getOriginal(edit.getReg())
      • collectRegsToSpill()：除了主寄存器，还会把拆分出的“snippet”一并 spill，以便后续折叠。
    2. 尝试重物化（reMaterializeAll()）
      • 对于可以重算（remat）的定义，优先在用点前插入定义指令，而非 reload。
    3. 真正插入 spill/reload（spillAll()）
      • 为主寄存器分配（或复用）同一栈槽；
      • 对每次使用点调用 spillAroundUses(Reg)：
        • foldMemoryOperand()：尝试把 LOAD/STORE 折叠进目标指令；
        • 否则用 insertReload() + 重写后续指令中的寄存器操作；
        • 用 insertSpill() 在写后插入 STORE。
      • 调用 HSpiller.hoistAllSpills() 做跨块提 early chance。
      • 清理所有死掉的 snippet 和定义，更新 LiveIntervals。
  • 几个最核心的 API
    • BuildMI(…, TargetOpcode::INIT_UNDEF/IMPLICIT_DEF)：初始化伪定义
    • TII.storeRegToStackSlot / TII.loadRegFromStackSlot：插入 spill/reload
    • TII.foldMemoryOperand：折叠独立的 spill/reload 到相邻指令
    • LiveRangeEdit::createFrom、rematerializeAt：动态创建新 vreg 并做重物化
    • DeadLaneDetector 与子寄存器合并（在更细粒度上补全 undef）