7.6 KiB

Raw Permalink Blame History Unescape Escape

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

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

1. 完成内容概览

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

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

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

Mem2Reg -> ConstFold -> ConstProp -> ConstFold -> DCE

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

2. Mem2Reg 做了什么

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

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

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

例如：

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

提升后核心 IR 会变成：

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 核心算法

实现流程如下：

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

2.3 修过的问题

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

原来 phi 名字类似：

变量名.phi

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

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

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

%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

例如：

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

会变成：

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. 测试脚本设计

新增或重写的脚本：

scripts/verify_mem2reg.sh

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

脚本分三层验证。

5.1 IR 生成检查

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

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

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

5.2 优化结果检查

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

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

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

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

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

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

5.3 运行语义回归

第三层需要手动打开：

./scripts/verify_mem2reg.sh --run

它会执行：

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

脚本比较时会统一处理：

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

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

6. 测试脚本用法

6.1 构建项目

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

6.2 只检查 pass 能否跑完

./scripts/verify_mem2reg.sh

默认会扫描：

test/

输出示例：

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

6.3 同时运行语义回归

./scripts/verify_mem2reg.sh --run

输出示例：

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

6.4 只测试某个目录

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

6.5 打印详细信息

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

6.6 严格检查 mem2reg

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

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

7. 当前测试结论

当前执行：

./scripts/verify_mem2reg.sh --run

结果为：

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 名字唯一性、基本块前驱匹配等问题。

7.6 KiB Raw Permalink Blame History Unescape Escape