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

难度：高

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

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

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

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：撰写设计文档，包含算法步骤、溢出策略、性能评测。