# Lab4 工作记录：基本标量优化

本文记录本次 Lab4 中完成的优化 pass、关键实现思路、遇到的问题和测试脚本的使用方式。

## 1. 完成内容概览

本次主要完成并接入了如下内容：

- `Mem2Reg`：将可提升的局部标量变量从 `alloca/load/store` 形式提升到 SSA 形式。
- `ConstFold`：对常量表达式进行编译期求值。
- `ConstProp`：做简单常量传播和代数化简。
- `DCE`：删除没有 use 且没有副作用的死指令。
- `verify_mem2reg.sh`：批量验证 `test/` 下所有用例是否能完成现有 pass 优化，并可选运行语义回归。

当前优化流水线接在 `src/irgen/IRGenDriver.cpp` 中，顺序为：

```text
Mem2Reg -> ConstFold -> ConstProp -> ConstFold -> DCE
```

其中第二次 `ConstFold` 用于吃掉 `ConstProp` 暴露出来的新常量表达式，最后的 `DCE` 清理被替换后不再使用的指令。

## 2. Mem2Reg 做了什么

前端生成 IR 时，局部变量通常先表示成内存形式：

```llvm
%x = alloca i32
store i32 1, i32* %x
%v = load i32, i32* %x
```

这种形式语义直接，但会让后续优化很难判断 `%v` 到底是什么值。`Mem2Reg` 的作用是把这类可提升变量改写成 SSA value。

例如：

```c
int x;
if (cond) {
  x = 1;
} else {
  x = 2;
}
return x;
```

提升后核心 IR 会变成：

```llvm
merge:
  %x.merge.phi0 = phi i32 [1, %then], [2, %else]
  ret i32 %x.merge.phi0
```

`phi` 表示“根据控制流从哪个前驱块来，选择对应的值”。

### 2.1 可提升对象

本实验里的 `Mem2Reg` 只提升局部标量 alloca：

- `i32*`
- `float*`
- `i1*`

并且要求它们只被直接 `load/store` 使用。

以下情况不会提升：

- 数组 alloca，例如 `[100 x i32]`
- 通过 `getelementptr` 复杂访问的内存
- 地址传给函数的变量
- 全局变量
- 其他地址逃逸的变量

所以测试中仍看到数组相关 `alloca` 是正常的。`mem2reg` 不是把所有内存都消掉，而是把可以安全转成 SSA 的局部标量消掉。

### 2.2 核心算法

实现流程如下：

1. 扫描入口块，找到可提升的 `alloca`。
2. 收集该变量所有 `store` 所在的定义块。
3. 构建 CFG，并计算支配树和支配边界。
4. 在支配边界处插入 `phi`。
5. 沿支配树递归重命名：
   - 遇到 `store`，更新当前变量值。
   - 遇到 `load`，用当前变量值替换该 `load`。
   - 遍历后继块时，给后继块中的 `phi` 填 incoming value。
6. 删除被提升掉的 `alloca/load/store`。

### 2.3 修过的问题

实现过程中修了一个关键问题：多个 phi 结果重名。

原来 phi 名字类似：

```text
变量名.phi
```

复杂循环里同一个变量可能需要多个 phi，导致 LLVM 报：

```text
multiple definition of local value named '...phi'
```

现在 phi 名字包含变量名、基本块名和递增编号，例如：

```text
%t45_i.while.cond.t72.phi3
```

这样可以保证同一个函数内 SSA 名字唯一。

## 3. 常量折叠与常量传播

### 3.1 ConstFold

`ConstFold` 会把操作数都是常量的指令直接计算出来，并用常量替换原指令。

目前支持：

- 整数运算：`add/sub/mul/div/mod/and/or`
- 浮点运算：`fadd/fsub/fmul/fdiv`
- 整数比较：`icmp`
- 浮点比较：`fcmp`
- 类型转换：`zext/trunc/sitofp/fptosi`
- 所有 incoming 都是同一常量的简单 `phi`

例如：

```llvm
%t = add i32 20, 4
ret i32 %t
```

会变成：

```llvm
ret i32 24
```

### 3.2 ConstProp

`ConstProp` 主要做简单代数化简和传播：

- `x + 0 -> x`
- `x - 0 -> x`
- `x * 1 -> x`
- `x * 0 -> 0`
- `x / 1 -> x`
- `0 / x -> 0`
- `phi` 所有有效 incoming 相同，则替换为该值

它不做复杂全局数据流分析，目标是配合 `Mem2Reg` 暴露出来的 SSA 值，吃掉一些明显冗余表达式。

## 4. DCE

`DCE` 删除无副作用且没有 use 的指令。

保留的有副作用或控制流指令包括：

- `store`
- `ret`
- `call`
- `br`
- `condbr`

优化后被常量替换掉的二元运算、比较、转换指令，如果不再被使用，会被 DCE 清掉。

## 5. 测试脚本设计

新增或重写的脚本：

```text
scripts/verify_mem2reg.sh
```

这个脚本不再只测试 `test/test_case/mem2reg`，而是默认扫描整个 `test/` 目录下所有 `.sy` 文件。

脚本分三层验证。

### 5.1 IR 生成检查

第一层检查每个 `.sy` 是否能完成：

```bash
./build/bin/compiler --emit-ir xxx.sy
```

如果能生成包含 `define` 的 IR，说明前端和当前 pass 流水线都跑完了。

### 5.2 优化结果检查

第二层检查优化后 IR 中是否还有标量 alloca：

```llvm
%x = alloca i32
%y = alloca float
%b = alloca i1
```

默认情况下，残留标量 alloca 只作为 warning，不直接判失败。原因是：不是所有 alloca 都一定能安全提升，尤其在复杂数组、地址使用、函数调用附近，保守处理是合理的。

如果希望更严格，可以使用：

```bash
./scripts/verify_mem2reg.sh --strict-mem2reg
```

这会把残留标量 alloca 当成失败。

### 5.3 运行语义回归

第三层需要手动打开：

```bash
./scripts/verify_mem2reg.sh --run
```

它会执行：

1. 生成优化后 IR。
2. 用 `llc` 把 `.ll` 转成目标文件。
3. 用 `clang` 链接目标文件。
4. 如果存在 `sylib/sylib.c`，会先编译并链接运行库。
5. 自动读取同名 `.in` 作为输入。
6. 将程序 stdout 和退出码拼成 actual 结果。
7. 与同名 `.out` 对比。

脚本比较时会统一处理：

- Windows 风格换行 `\r\n`
- 文件末尾是否多一个换行

这样可以避免因为文本格式差异造成误报。

## 6. 测试脚本用法

### 6.1 构建项目

```bash
cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build -j "$(nproc)"
```

### 6.2 只检查 pass 能否跑完

```bash
./scripts/verify_mem2reg.sh
```

默认会扫描：

```text
test/
```

输出示例：

```text
IR 生成:       22 / 22
Pass 优化检查: 22 / 22
全部检查通过。
```

### 6.3 同时运行语义回归

```bash
./scripts/verify_mem2reg.sh --run
```

输出示例：

```text
IR 生成:       22 / 22
Pass 优化检查: 22 / 22
运行结果:      22 / 22
全部检查通过。
```

### 6.4 只测试某个目录

```bash
./scripts/verify_mem2reg.sh --test-root test/test_case/functional --run
```

### 6.5 打印详细信息

```bash
./scripts/verify_mem2reg.sh --debug --run
```

### 6.6 严格检查 mem2reg

```bash
./scripts/verify_mem2reg.sh --strict-mem2reg
```

这个模式适合专门检查“还有哪些标量 alloca 没被提升”。当前某些复杂性能样例会有 warning，是否要继续优化要结合 IR 使用情况判断。

## 7. 当前测试结论

当前执行：

```bash
./scripts/verify_mem2reg.sh --run
```

结果为：

```text
IR 生成:       22 / 22
Pass 优化检查: 22 / 22
运行结果:      22 / 22
全部检查通过。
```

这说明：

- 所有测试都能完成当前 pass 流水线。
- 生成的 IR 能被 LLVM 工具链接受。
- 链接运行库后，程序输出和退出码均与 `.out` 匹配。

脚本中出现的标量 alloca warning 不影响当前语义正确性，它们只是提示后续还有进一步提升或更精细逃逸分析的空间。

## 8. 后续可改进方向

后续如果继续扩展 Lab4，可以考虑：

- 为 `Mem2Reg` 增加更完整的可提升性分析。
- 对未初始化 load 做更稳健的默认值处理。
- 增加 CFG Simplify，删除常量条件分支和不可达块。
- 增加 CSE，消除重复表达式。
- 将常量折叠和传播做成迭代到不动点。
- 增加 IR verifier，提前检查 phi incoming 数量、SSA 名字唯一性、基本块前驱匹配等问题。