112 lines
6.7 KiB
Markdown
112 lines
6.7 KiB
Markdown
# Lab4：基本标量优化
|
||
|
||
## 1. 本实验定位
|
||
|
||
为了提升最终生成汇编码的实际运行性能，本实验需要引入基础标量优化；这一部分优化通常能够带来较为明显的性能提升。
|
||
在进入本实验的标量优化前，先完成或接入 `mem2reg`，将局部变量的 `alloca/load/store` 提升到 SSA 形式。
|
||
|
||
在此基础上，可以逐步补上常量相关优化、无用代码删除、CFG 简化、公共子表达式消除等基础标量优化；如果你的实现方案里还需要其他局部优化，也可以按需继续扩展。
|
||
|
||
## 2. Lab4 要求
|
||
|
||
需要同学完成的事情并不复杂：先理解当前 IR/CFG 结构，然后实现能够运行的基础标量优化，并把这些优化接入 `PassManager`，形成可重复执行的流程；最后通过测试确认优化前后语义一致。
|
||
|
||
## 3. 相关文件
|
||
|
||
以下文件与本实验内容相关，建议优先阅读。
|
||
|
||
- `include/ir/IR.h`
|
||
- `src/ir/passes/Mem2Reg.cpp`
|
||
- `src/ir/passes/ConstFold.cpp`
|
||
- `src/ir/passes/ConstProp.cpp`
|
||
- `src/ir/passes/DCE.cpp`
|
||
- `src/ir/passes/PassManager.cpp`
|
||
|
||
## 4. 当前基础与前置准备
|
||
|
||
### 4.1 Mem2Reg
|
||
|
||
在很多编译器中，AST lower 到 IR 时，局部变量通常先以“内存形式”表示，也就是先用 `alloca` 在栈上分配局部变量，再通过 `store/load` 完成写入和读取。
|
||
这种表示语义正确、实现直接，但会引入大量冗余内存访问，不利于常量传播、DCE、CSE 等标量优化。
|
||
|
||
`mem2reg`（memory to register）的目标，就是把这类 `alloca/load/store` 形式提升到 SSA 形式，让值尽量直接在 SSA Value 上传递。
|
||
|
||
#### 4.1.1 Mem2Reg 的核心过程
|
||
|
||
典型流程通常包括几步：先识别可提升变量，找出由 `alloca` 分配且只通过 `load/store` 访问的局部变量；再构建 CFG，明确基本块与前驱/后继关系，为后续插入 `phi` 和重命名提供基础；接着在控制流汇合点插入 `phi`，并沿支配树完成变量重命名，为每次定义分配 SSA 版本；最后删除已经被提升掉的冗余 `alloca/load/store`。
|
||
|
||
#### 4.1.2 Mem2Reg 的关键算法基础
|
||
|
||
支配树（Dominator Tree）用于描述“定义能影响到哪里”。若从入口到块 A 的所有路径都经过块 B，则 B 支配 A；变量重命名通常就建立在这层关系上，常见实现可采用 Lengauer-Tarjan 等算法。
|
||
|
||
支配边界（Dominance Frontier）描述的是“支配关系结束并发生控制流汇合”的位置。在 Mem2Reg 中，它的核心作用是确定 `phi` 函数插入点。
|
||
|
||
如果从更高层去看，Mem2Reg 本质上就是 SSA 构造流程在“可提升局部变量”上的工程化实现。典型路线仍然是：计算支配树，计算支配边界，插入 `phi`，再完成变量重命名。
|
||
|
||
### 4.2 IR 的 use-def 关系
|
||
|
||
LLVM 中通常维护完整 `Use-User` 双向关系；当前仓库是最小 IR，实现较轻量。
|
||
|
||
#### 4.2.1 什么是 use-def
|
||
|
||
use-def（或 def-use）描述的是“值在哪里被定义、又在哪里被使用”的关系。`def` 指某条指令产生了一个值，`use` 指其他指令把这个值当作操作数使用。
|
||
|
||
在 IR 中维护好这层关系后，优化遍就能更快回答“这个值还有人用吗”“我要把旧值替换成新值，需要改哪些地方”这类问题。
|
||
|
||
#### 4.2.2 use-def 的作用
|
||
|
||
在优化阶段，use-def 关系的价值主要体现在几个方面：判断一个值是否还被使用会更直接，DCE 不必反复做全函数扫描；常量折叠、常量传播、复制传播这类局部重写也更容易精准找到所有使用点；同时，它还能降低很多优化遍的实现复杂度，并为后续扩展代数化简、CSE、部分冗余消除等优化打基础。
|
||
|
||
因此，把这层关系维护稳定，通常会明显降低 DCE、常量传播等优化的实现难度，也更利于后续扩展。
|
||
|
||
## 5. 可实现的优化方向与实现提示
|
||
|
||
### 5.1 Constant Folding / Constant Propagation
|
||
|
||
常量相关优化通常包括常量折叠（Constant Folding）与常量传播（Constant Propagation）。前者是指当一条指令的操作数已经都是常量时，直接在编译期计算结果并用常量替换原指令；后者是指当某个 SSA 值已知为常量时，将该常量继续传播到其使用点，从而为后续进一步折叠、删除冗余分支和清理死代码创造条件。
|
||
|
||
### 5.2 Dead Code Elimination (DCE)
|
||
|
||
可以采用“标记 + 清扫”思路：先从会影响程序可观察行为的指令出发，标记为“有用”指令，例如 ret、分支跳转、store 以及可能具有副作用的 call；再沿这些指令的数据依赖反向传播，将其依赖的定义一并标记为有用；最后删除其余未被标记、且本身不具有副作用的指令。
|
||
> 本实验不限定具体思路，实现可自由设计。
|
||
|
||
### 5.3 CFG Simplification
|
||
|
||
在 DCE 之后，通常还需要对 CFG 做一轮结构化清理，例如改写冗余分支、删除或绕过空块、合并线性可拼接的基本块，以及清理不可达块。
|
||
|
||
### 5.4 公共子表达式消除（Common Subexpression Elimination）
|
||
|
||
如果同一个表达式在程序中被多次计算，并且其操作数在计算之间没有改变，那么就可以只计算一次并复用结果。这类优化的直接收益，是减少重复计算、压缩指令数量、提升执行效率。实现时，通常会在基本块或更大范围内记录已经出现过的表达式；当再次遇到相同表达式且操作数未变化时，直接复用之前的结果，而不是重新生成同一计算。
|
||
|
||
### 5.5 优化顺序建议
|
||
|
||
这里建议只固定一个基本约束：先执行一遍 `Mem2Reg`，把 IR 提升到更适合做标量优化的形式。
|
||
|
||
其余优化遍（如 `ConstFold`、`CSE`、`DCE`、`CFGSimplify`）的组织顺序不做硬性规定，可根据你的实现自由设计；可以采用优化遍多次迭代方式，直到 IR 不再变化。
|
||
|
||
|
||
## 6. 构建与验证
|
||
|
||
```bash
|
||
cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
|
||
cmake --build build -j "$(nproc)"
|
||
```
|
||
|
||
### 6.1 观察 IR
|
||
|
||
```bash
|
||
./build/bin/compiler --emit-ir test/test_case/functional/simple_add.sy
|
||
```
|
||
|
||
这条命令只适合先观察单个样例的 IR 形态。完成 Lab4 后，不能只检查 `simple_add`，还应覆盖 `test/test_case` 下全部测试用例。
|
||
|
||
### 6.2 语义回归
|
||
|
||
```bash
|
||
./scripts/verify_ir.sh test/test_case/functional/simple_add.sy test/test_result/function/ir --run
|
||
./scripts/verify_asm.sh test/test_case/functional/simple_add.sy test/test_result/function/asm --run
|
||
```
|
||
|
||
目标：脚本自动读取同名 `.in`，并将程序输出与退出码和同名 `.out` 比对，确保优化后程序行为与优化前保持一致。
|
||
完成 Lab4 后，应对 `test/test_case` 下全部测试用例逐个回归；如有需要，也可以自行编写批量测试脚本统一执行。
|