课题17：寄存器分配（基本块内线性扫描）

难度：高 | 类型：项目实战 | 源文件：scratchv/backend/regalloc_linear.py | 行数：~500 状态：✅ 已完成

概述

为每个基本块内的虚拟寄存器分配真实的RISC-V物理寄存器（x1~x31），并在不够用时插入溢出（spill）代码。

---

理解背景

是什么？

寄存器分配器把指令中使用的无限多虚拟寄存器（vreg）映射到有限多的物理寄存器（a0-a7, t0-t6, s0-s11）。当物理寄存器不够用时，自动插入"溢出代码"——把暂时不用的值存到栈上，需要时再加载回来。

指令选择输出: ADD v3, v1, v2     ← 虚拟寄存器 (有无穷多个)
        ↓
    寄存器分配
        ↓
汇编输出:    ADD a0, t1, t2      ← 物理寄存器 (只有 ~25 个可用)

为什么？

CPU 只有有限的寄存器（RISC-V 32 位有 32 个，排除 x0/sp/gp/tp/ra 剩下 25 个可分配）。编译器的代码生成阶段为了方便，假设有无穷多个虚拟寄存器。寄存器分配器负责把"无穷"映射到"有限"。

类比：你有一个 25 格的文件架，但可能有 100 份文件需要处理。你需要不断把不用的文件放回文件柜（溢出到栈），把要用的文件拿出来（从栈加载）。

核心概念

1. 活跃区间（Live Interval）

每个虚拟寄存器有一个"从出生到死亡"的区间：

v1:  [0 ───────── 5]     ← 在指令0被定义，在指令5最后使用
v2:     [1 ─── 3]         ← 在指令1被定义，在指令3最后使用
v3:         [2 ────── 6]

两个区间重叠 = 两个变量同时活跃 = 它们不能共享同一个物理寄存器。

2. 线性扫描算法

1. 计算所有变量的活跃区间（按开始位置排序）
2. 维护一个 "active" 列表（当前活跃的区间，按结束位置排序）
3. 逐个处理区间:
   a. 从 active 中"过期"那些 end <= 当前区间.start 的区间 → 释放寄存器
   b. 如果有空闲寄存器 → 分配
   c. 如果没有 → 溢出 active 中结束最晚的区间
4. 为被溢出的变量插入 spill code (sw/lw)

3. 溢出策略（Spill）

当寄存器满了，必须选择一个变量"溢出"到栈上。选择策略是：溢出活跃区间结束最晚的那个。

为什么？因为溢出一个"快要用完"的变量（结束早）可能刚溢出又要加载回来，而溢出"还要用很久"的变量更划算——一次溢出，省出寄存器供多个变量使用。

4. RISC-V 可分配寄存器

组	寄存器	数量	特点
参数/临时	a0-a7, t0-t6	15	调用者保存
保留	s0-s11	12	被调用者保存
总计可分配		27	排除 x0, sp, gp, tp, ra

---

详细任务

1. 分析基本块内每个虚拟寄存器的活跃区间（定义点到最后一个使用点）。
2. 实现线性扫描算法：按起始点排序，维护活跃区间列表，分配物理寄存器。
3. 当物理寄存器不足时，选择溢出变量（最晚结束的区间），存入栈中，需要时重新加载。
4. 生成溢出加载/存储指令，更新栈帧偏移。
5. 与现有代码生成集成，添加--regalloc=linear选项。

---

交付产物

• regalloc_linear.py模块
• 测试程序（大量变量），对比优化前后汇编代码
• 文档：算法描述、使用方法

---

代码走读

Step 1: 理解活跃区间

from scratchv.backend.regalloc_linear import LinearScanAllocator, LsInstruction

# 3 条指令，3 个虚拟寄存器
block = [
    LsInstruction(0, "add", ["v1", "v2", "v3"], defines={"v1"}, uses={"v2","v3"}),
    LsInstruction(1, "mul", ["v4", "v1", "v5"], defines={"v4"}, uses={"v1","v5"}),
    LsInstruction(2, "add", ["v6", "v4", "v1"], defines={"v6"}, uses={"v4","v1"}),
]

allocator = LinearScanAllocator()
intervals = allocator.compute_live_intervals(block)

for iv in intervals:
    print(f"{iv.vreg}: [{iv.start}, {iv.end}) uses={iv.uses}")

输出：

v2: [0, 1) uses={0}      ← 只在指令0被使用
v3: [0, 1) uses={0}      ← 只在指令0被使用
v1: [0, 3) uses={1, 2}   ← 从指令0到指令2一直活跃
v5: [1, 2) uses={1}      ← 只在指令1被使用
v4: [1, 3) uses={2}      ← 从指令1到指令2活跃
v6: [2, 3) uses={}       ← 只有定义，没有使用？

Step 2: 执行寄存器分配

mapping = allocator.allocate(intervals)
for vreg, preg in mapping.items():
    print(f"{vreg} → {preg}")

# 查看分配报告
print(allocator.report())

Step 3: 生成分配后的汇编

code = allocator.get_allocated_code(block)
print(code)

---

Live Interval 计算

def compute_live_intervals(self, block):
    intervals = {}
    for i, instr in enumerate(block):
        for def_reg in instr.defines:
            if def_reg not in intervals:
                intervals[def_reg] = LiveInterval(vreg=def_reg, start=i, end=i+1)
            else:
                intervals[def_reg].start = min(intervals[def_reg].start, i)
        for use_reg in instr.uses:
            if use_reg in intervals:
                intervals[use_reg].end = max(intervals[use_reg].end, i + 1)
                intervals[use_reg].uses.add(i)
    return sorted(intervals.values(), key=lambda iv: iv.start)

核心分配循环

def allocate(self, intervals):
    active = []  # (end_pos, preg, interval)
    free_regs = list(self.phys_regs)

    for current in intervals:
        # 1. 过期检查：释放不再活跃的区间占用的寄存器
        active = [(e, p, iv) for e, p, iv in active if e > current.start]
        # 将释放的寄存器还给 free_regs

        # 2. 分配
        if free_regs:
            preg = free_regs.pop(0)
            mapping[current.vreg] = preg
            active.append((current.end, preg, current))
        else:
            # 3. 溢出：选择 end 最远的
            active.sort(key=lambda x: -x[0])
            _, spilled_preg, spilled_iv = active[0]
            # 标记 spilled_iv 为溢出，将 spilled_preg 分配给 current
            mapping[current.vreg] = spilled_preg
            self._spills.add(spilled_iv.vreg)

    return mapping

Spill Code 生成

def _gen_spill_code(self, vreg, preg):
    """为溢出的虚拟寄存器插入 sw/lw"""
    offset = self._alloc_stack_slot(vreg)
    # 在每次定义后插入: sw preg, offset(sp)
    # 在每次使用前插入: lw preg, offset(sp)

---

动手练习

练习 1: 手算活跃区间

写 5 条指令（3 个虚拟寄存器），手工画出每个寄存器的活跃区间，然后用代码验证。

练习 2: 观察溢出

用 30 个虚拟寄存器但只有 5 个物理寄存器，运行 allocator，观察哪些寄存器被溢出、溢出了几次。

练习 3: 改进溢出策略

尝试修改溢出策略：不是溢出 end 最远的，而是溢出使用次数最少的。比较两种策略的总溢出次数。

---

常见坑

坑	说明
基本块内 vs 全局	当前算法只在单个基本块内分配，跨基本块的变量（跨越 CFG 边）需要全局寄存器分配（图着色）
活跃区间精度	end 是半开区间 [start, end)，end 位置表示"最后使用之后就不再活跃"
寄存器压力	Conv2D 的 6 层嵌套循环中寄存器压力极大（需要同时持有 input_ptr, weight_ptr, acc, loop counters 等），容易频繁溢出
调用约定	a0-a7 是调用者保存（caller-saved），s0-s11 是被调用者保存（callee-saved）。跨函数调用时需要正确保存/恢复

---

进阶阅读

• 龙书第 8.8 节：Register Allocation
• Poletto & Sarkar (1999): Linear Scan Register Allocation (ACM TOPLAS)
• RISC-V ABI: psABI Register Convention
• 相关 topic: 课题8 — 指令选择 | 课题11 — 控制流图生成器 | 课题18 — 指令调度器

---

12周每周目标

• W1：学习寄存器分配基本概念：虚拟寄存器、物理寄存器、活跃区间、溢出。
• W2：分析项目现有的寄存器分配（如果有）或当前代码生成如何使用虚拟寄存器。
• W3：为每个基本块提取所有虚拟寄存器的定义和使用点，计算活跃区间（从定义到最后一次使用）。
• W4：实现活跃区间计算：遍历IR，记录每个虚拟寄存器的起始和结束位置。
• W5：实现线性扫描：将所有区间按起始点排序，维护活跃列表，分配物理寄存器（x1-x31）。
• W6：实现溢出策略：当物理寄存器不够时，选择最晚结束的区间溢出。
• W7：实现溢出代码生成：在定义后插入sw存储到栈，在使用前插入lw加载，维护栈槽分配。
• W8：实现物理寄存器替换：将虚拟寄存器替换为分配的物理寄存器，注意保留x0和ra等。
• W9：处理调用约定：被调用者保存寄存器（如x8-x9）需要在函数入口保存、出口恢复。
• W10：集成到代码生成阶段，在生成RISC-V指令前进行寄存器分配，添加--regalloc=linear选项。
• W11：测试简单函数（少量变量），验证生成的汇编使用了物理寄存器且无冲突。
• W12：撰写设计文档，包含算法步骤、溢出策略、性能评测。