# Lab4-Lab6 完成情况说明

## 1. 文档目的

本文档用于对照 `doc/Lab4-基本标量优化.md`、`doc/Lab5-寄存器分配.md`、`doc/Lab6-并行与循环优化.md`，说明当前编译器在 Lab4、Lab5、Lab6 三个阶段的完成情况，并补充最近一轮围绕比赛级目标所做的修改与优化。

## 2. 总体结论

从当前代码状态看：

- Lab4：已完成，且已经超过文档中的基础标量优化要求。
- Lab5：已完成，且已经形成真实可运行的后端寄存器分配与后端优化链路，不再是示例级后端。
- Lab6：主体已完成，已经具备比赛可用的单线程循环优化能力；循环并行分析基础已接入，但未实现真正的多线程运行时并行执行。

当前主线已经是：

`SysY -> IR 生成 -> IR 优化 -> MIR lowering -> MIR 优化 -> 寄存器分配 -> 栈帧落地 -> AArch64 汇编输出`

## 3. 对照完成情况

### 3.1 Lab4：基本标量优化

Lab4 文档要求的核心是：

1. 先做 `mem2reg`，把局部变量提升到 SSA。
2. 实现基础标量优化，如常量折叠、常量传播、DCE、CFG 简化、CSE。
3. 把这些优化接入 `PassManager`，形成可重复执行的优化流程。
4. 通过测试确认优化前后语义一致。

当前实现情况：

- `Mem2Reg` 已接入优化流水线，并作为标量优化前置步骤执行。
- `ConstProp`、`ConstFold`、`DCE`、`CFGSimplify`、`CSE` 均已实现并接入。
- 在文档要求之外，又新增了 `GVN` 与 `LoadStoreElim`，进一步加强了内存相关和跨块冗余消除能力。
- `PassManager` 已形成迭代优化流程，而不是单次串行跑一遍后结束。

当前 `IR` 流水线在 `src/ir/passes/PassManager.cpp` 中会迭代执行：

- `RunFunctionInlining`
- `RunConstProp`
- `RunConstFold`
- `RunGVN`
- `RunLoadStoreElim`
- `RunCSE`
- `RunDCE`
- `RunCFGSimplify`
- `RunLICM`
- `RunLoopStrengthReduction`
- `RunLoopFission`
- `RunLoopUnroll`

完成判断：

- Lab4 已完成。
- 严格按文档要求看，不仅满足“基础标量优化”要求，而且已经扩展到了更强的中端优化框架。

### 3.2 Lab5：寄存器分配与后端优化

Lab5 文档要求的核心是：

1. MIR 不再固定使用少量物理寄存器，而是先生成虚拟寄存器。
2. 实现真实寄存器分配，并处理 spill/reload、callee-saved、栈槽等问题。
3. 接入后端局部优化流程，减少冗余 `copy/move`、冗余 `load/store` 和明显恒等指令。
4. 在全部测试上验证正确性，并尽量提升生成代码质量。

当前实现情况：

- `Lowering` 已经输出虚拟寄存器 MIR，而不是固定寄存器模板。
- `RegAlloc` 已实现真实寄存器分配，当前采用图着色风格分配流程，并处理了：
  - 活跃性分析
  - 干涉关系
  - `copy` 合并
  - spill 栈槽分配
  - callee-saved 保存恢复信息回填
  - live-across-call 约束
- `FrameLowering` 与 `AsmPrinter` 已经能够围绕 RA 结果完成最终栈帧和汇编输出。
- `MIR` 优化流水线已经真正接入主链：
  - `PreRA`：`AddressHoisting + Peephole`
  - `PostRA`：`Peephole`

后端局部优化目前已经覆盖：

- 冗余 `copy` 消除
- 恒等算术指令消除
- 条件跳转简化
- 局部冗余 `load/store` 消除
- 同块内 store-to-load forwarding
- 同地址重复 `store` 删除
- 基于 CFG 的跨块 memory dataflow

最近一轮后端进一步做了两件关键事情：

1. `MIR Peephole` 从“单基本块局部优化”提升到“带 CFG 数据流的跨块内存优化”。
2. `MIR Lowering` 调整为按可达 CFG 顺序 lowering，修复了内联后复杂 CFG 下 SSA 值先用后定义导致的 lowering 失败。

说明：

- 曾尝试扩展 `v16-v18` 作为额外 FPR 可分配寄存器，但在浮点重调用样例上出现错误，因此最终回退，保留稳定寄存器集合。这一调整没有留在主线中。

完成判断：

- Lab5 已完成。
- 与文档中的“最小后端推进到真实后端”目标相比，当前实现已经超过课程最低线。

### 3.3 Lab6：并行与循环优化

Lab6 文档要求的核心是：

1. 建立循环分析基础，识别循环头、循环体、前置块、退出块、回边等结构。
2. 实现有效循环优化，并接入 `PassManager`。
3. 与 Lab4 标量优化协同工作。
4. 若希望进一步提升性能，可继续尝试可并行循环识别与并行化。

当前实现情况：

- 已实现 `DominatorTree` 与 `LoopInfo`，可识别自然循环及其层次关系。
- 已补齐循环变换所需的 `LoopPassUtils`。
- 已接入的循环优化包括：
  - `LICM`
  - `LoopStrengthReduction`
  - `LoopUnroll`
  - `LoopFission`
- `LoopMemoryUtils` 已从较弱的循环地址分析，升级为结合：
  - simple induction variable
  - affine 地址表达
  - exact-address key
  - root-aware alias/mod-ref
  - 非逃逸局部对象分析
  的更强版本。
- `LICM` 已经可以更积极地 hoist 安全的 `load`，并对同地址的 hoisted load 做去重合并。

关于“并行与循环优化”中的并行部分：

- 当前已经具备可并行循环识别与依赖分析基础。
- 但没有继续接入真正的多线程并行 runtime，也没有把循环改写为可直接并发执行的运行时调用。
- 结合文档表述，这部分更像“继续深入方向”，而不是 Lab6 基础完成线的硬要求。

完成判断：

- Lab6 主体已完成。
- 从比赛级编译器角度，当前已经具备较完整的单线程循环优化能力。
- 若以“真正运行时并行执行”作为额外目标，则这一部分仍可继续扩展，但不影响当前对 Lab6 主体完成的判断。

## 4. 最近一轮修改与优化

这一轮围绕比赛级目标，主要新增和加强了以下内容。

### 4.1 中端新增与增强

- 新增 `GVN`，用于更大范围复用纯表达式结果。
- 新增 `LoadStoreElim`，支持跨块冗余 `load` 消除、store-to-load forwarding、死 `store` 删除。
- 强化 `LoopMemoryUtils`，让循环内存优化不再只依赖很保守的规则。
- 强化 `LICM`，使其对安全 `load` 的外提更积极，并能对 hoisted load 做合并。
- 新增 IR 级小函数内联，使收益更早反馈到 `ConstProp`、`GVN`、`DCE`、`LICM` 等中端优化。

### 4.2 后端新增与增强

- `MIR Peephole` 从局部块内优化，扩展到基于 CFG 的跨块内存状态传播。
- `Call` 现在会按源 `IR Function` 的 effect 信息进行 `read/write` 边界判断，不再统一按最粗粒度处理。
- 修复了内联后复杂控制流下 MIR lowering 的块顺序问题。
- 完整回归后保留稳定 FPR 集合，放弃了不稳定的 `v16-v18` 扩容方案。

### 4.3 这轮优化的实际意义

这意味着最近的修改已经不只是“补课程实验功能”，而是开始面向比赛收益去提升：

- 中端：更强的冗余消除、内存优化、函数级优化、循环优化协同
- 后端：更强的 `copy/load/store` 消除与更稳定的 RA 后局部优化

## 5. 当前验证情况

本次回归中，已经完成以下验证：

### 5.1 全量正确性回归

执行：

```bash
./scripts/lab3_build_test.sh test/test_case/functional test/test_case/h_functional
```

结果：

- `134 PASS / 0 FAIL / total 134`

这说明当前 Lab4-Lab6 优化接入后，完整 `asm` 路径在 `functional + h_functional` 上保持正确。

### 5.2 性能热点抽测

执行并通过：

- `test/test_case/h_performance/fft2.sy`
- `test/test_case/h_performance/matmul3.sy`
- `test/test_case/h_performance/transpose2.sy`
- `test/test_case/h_performance/gameoflife-gosper.sy`

这些样例覆盖了：

- 重循环
- 重访存
- 浮点运算
- 矩阵访问
- 较复杂控制流

可以说明当前新增优化至少在一批代表性性能样例上保持了可运行与结果正确。

## 6. 结论

综合来看，当前编译器在 Lab4、Lab5、Lab6 上的完成情况可以概括为：

- Lab4：完成，并已扩展到更强的中端优化。
- Lab5：完成，并已形成真实可运行的后端优化链路。
- Lab6：主体完成，单线程循环优化能力已经达到比赛可用水平。

如果后续继续朝比赛方向推进，最值得继续做的事情不再是“补实验是否完成”，而是：

1. 针对 `h_performance` 做系统 profiling。
2. 按性能热点继续优化中端内存/循环变换。
3. 继续提升后端 spill、copy、访存质量。
4. 如需继续深入 Lab6，可进一步尝试真正的并行 runtime 接入。