课题4：IR 优化器框架（5 Passes）
难度：中 | 类型：项目实战 | 源文件：
scratchv/optimizer/(5 passes) 状态：✅ 已完成
概述
IR 优化器框架包含 5 个 IR 层面的优化 pass：ConstantFolder（常量折叠）、DeadCodeEliminator（死代码消除）、IRPeepholeOptimizer（IR 窥孔）、MulAddFusion（乘加融合）、LICM（循环不变量外提）。所有 pass 共享统一接口（输入 Program，原地修改，返回变更计数），通过 PassManager 链式执行。
理解背景
是什么？
IR 优化器框架包含 5 个 IR 层面的优化 pass，它们共享相同接口：输入 Program，原地修改，返回变更计数。
优化前 IR → [ConstantFolder] → [DeadCodeEliminator] → [IRPeephole] → [MulAddFusion] → [LICM] → 优化后 IR
常量折叠 死代码消除 窥孔优化 乘加融合 循环不变量外提
为什么？
代码生成器（指令选择）是机械翻译——它不管你给它什么 IR，都会忠实地翻译。优化器的作用是在翻译之前先把 IR 变简洁。
例如生成器可能产生：
%1 = const 2
%2 = const 3
%3 = add %1, %2 # 常量折叠 → %3 = const 5
%4 = mul %5, %1 # %1 还能继续折叠
%6 = add %7, 0 # 恒等消除 → mv %6, %7
如果不做优化，后端会为这些冗余指令生成真实的机器码。
核心概念
五个优化 Pass
1. ConstantFolder（常量折叠）：编译时计算常量表达式。支持 ADD, SUB, MUL, DIV，要求全操作数为编译时常量。结果替换为 LOAD_CONST。
2. DeadCodeEliminator（死代码消除）：删除结果不被任何人使用的指令。从输出/副作用指令回溯标记"活的"指令，保留 STORE、RETURN、BR、BR_IF 等有副作用指令。迭代执行直到不动点。
3. IRPeepholeOptimizer（IR 窥孔）：局部模式替换。规则包括：add rd, rs, 0 → 删除、mul rd, rs, 1 → mv rd, rs、mul rd, rs, 0 → li rd, 0、以及冗余跳转消除。
4. MulAddFusion（乘加融合）：标记 mul→add 模式，为后端 FMA 提供提示。如果目标 ISA 支持 fmadd，后端可以发射单条指令。
5. LICM（循环不变量外提）：将循环内不依赖循环变量的计算移到循环前。一条指令是"循环不变量"当且仅当它的所有操作数都不依赖于循环变量。
详细任务
- 定义统一的 Pass 接口：
optimize(program: Program) -> int（返回变更次数）。
- 实现 PassManager：管理 pass 注册、链式执行、统计输出。
- 实现 ConstantFolder：检测 ADD/SUB/MUL/DIV 的全常量操作数，编译时计算并替换为 LOAD_CONST。支持迭代折叠。
- 实现 DeadCodeEliminator：use-def 回溯分析，标记副作用指令，迭代消除到不动点。
- 实现 IRPeepholeOptimizer：设计规则表（模式→替换），滑动窗口匹配，迭代到不动点。至少实现 5 条规则。
- 实现 MulAddFusion：识别 mul 指令的结果仅被一个 add 使用，且中间无其他使用者。标记 fused_mul_add 属性。
- 实现 LICM：检测 FOR/ENDFOR 循环体内的不变量（操作数不依赖循环变量）。将不变量指令移到循环前。
- 确保 Pass 执行顺序正确（折叠→死代码→窥孔→融合→LICM）。
- 添加 debug 输出和统计信息（每个 pass 的变更计数）。
- 对真实 CNN 模型测试优化效果，量化 IR 指令数减少。
交付产物
scratchv/optimizer/ — 5 个优化 pass 的实现scratchv/compiler.py — PassManager- 优化前后 IR 对比测试
- 文档：每个 pass 的规则说明、执行顺序原理
代码走读
优化 Pass 的统一接口
optimize(program: Program) -> int（返回变更次数）。scratchv/optimizer/— 5 个优化 pass 的实现scratchv/compiler.py— PassManager- 优化前后 IR 对比测试
- 文档：每个 pass 的规则说明、执行顺序原理
代码走读
优化 Pass 的统一接口
所有 pass 实现相同签名：
class OptimizationPass:
def optimize(self, program: Program) -> int:
"""对 Program 原地优化，返回变更次数"""
...
死代码消除的回溯标记
class DeadCodeEliminator:
def optimize(self, program):
used = set()
# 从每条"有副作用的"指令开始回溯
for instr in self._effectful_instructions(program):
self._mark_used(instr, used)
# 删除不在 used 集合中的指令
for block in all_blocks:
block.instructions = [i for i in block.instructions if i in used]
return removed_count
def _mark_used(self, instr, used):
if instr in used:
return
used.add(instr)
for op in instr.operands:
self._mark_used(op.defining_instruction, used) # 递归
LICM 的循环不变量检测
def _is_loop_invariant(self, instr, loop_var):
for op in instr.operands:
if op == loop_var: # 直接依赖循环变量
return False
if not op.is_constant: # 非常量，可能依赖循环变量
if not self._is_loop_invariant(op.defining_instruction, loop_var):
return False
return True
动手练习
练习 1: 写一个能被优化的 IR
class DeadCodeEliminator:
def optimize(self, program):
used = set()
# 从每条"有副作用的"指令开始回溯
for instr in self._effectful_instructions(program):
self._mark_used(instr, used)
# 删除不在 used 集合中的指令
for block in all_blocks:
block.instructions = [i for i in block.instructions if i in used]
return removed_count
def _mark_used(self, instr, used):
if instr in used:
return
used.add(instr)
for op in instr.operands:
self._mark_used(op.defining_instruction, used) # 递归
def _is_loop_invariant(self, instr, loop_var):
for op in instr.operands:
if op == loop_var: # 直接依赖循环变量
return False
if not op.is_constant: # 非常量，可能依赖循环变量
if not self._is_loop_invariant(op.defining_instruction, loop_var):
return False
return True
动手练习
练习 1: 写一个能被优化的 IR
手写一个包含 (2+3)*4 常量表达式和死代码的 IR，运行优化器，观察哪些指令被消除了。
练习 2: 添加新的窥孔规则
在 IRPeepholeOptimizer 中添加规则：sub rd, rs, 0 → mv rd, rs。
练习 3: 测量优化效果
对一个 DSL 程序分别以 "none" 和 "all" 级别编译，用指令计数器对比指令数变化。
常见坑
| 坑 | 说明 |
|---|---|
| Pass 执行顺序 | 顺序很重要。先折叠常量 → 再消除死代码（折叠后可能产生更多死代码）→ 再做 peephole。反过来可能遗漏优化机会 |
| 副作用指令 | STORE、BR 等不能被消除，即使它们的结果"看起来"没被使用 |
| LICM 的保守性 | 不确定是否为不变量时保守处理（留在循环内），宁可少优化不可错优化 |
| 不动点迭代 | DeadCodeEliminator 和 ConstantFolder 都要迭代到不动点——删除一条指令可能让另一条变成死代码 |
进阶阅读
- 龙书第 9 章：Machine-Independent Optimizations
- LLVM Pass 框架：Writing an LLVM Pass
- 相关 topic: 课题3 — IR 系统 | 课题13 — 窥孔优化器 | 课题8 — 指令选择
12周每周目标
- W1：学习编译器优化的基本概念：pass、迭代、不动点、use-def 链。阅读龙书第 9 章。阅读现有 5 个 pass 的源码。
- W2：实现统一的 Pass 接口（抽象基类
OptimizationPass）和 PassManager（注册、执行、统计）。支持 --opt-level none|basic|all 三级配置。
- W3：实现 ConstantFolder 第 1 版：检测 ADD/SUB 的双常量操作数。实现
_compute() 方法（支持 float32 和 int32）。
- W4：完善 ConstantFolder：添加 MUL/DIV 支持。实现递归折叠（折叠后的 LOAD_CONST 触发新一轮折叠）。迭代到不动点。
- W5：实现 DeadCodeEliminator：use-def 回溯分析。从 RETURN/STORE/BR 等副作用指令开始标记"活的"指令。实现
_mark_used() 的递归遍历。
- W6：完善 DeadCodeEliminator：处理复杂情况（循环内的死代码、跨基本块的 use-def）。迭代到不动点。
- W7：实现 IRPeepholeOptimizer：设计规则表数据结构（模式指令列表 + 替换指令列表）。实现滑动窗口匹配。至少实现 5 条规则。
- W8：实现 MulAddFusion：扫描 mul 指令，检查结果仅被一个 add 使用且无其他使用者。标记 fused_mul_add 属性。
- W9：实现 LICM：FOR/ENDFOR 循环体识别。循环不变量检测（依赖链分析）。安全外提（移到循环前，保持 SSA 正确）。
- W10：测试 Pass 链式执行：ConstantFolder → DeadCodeEliminator → IRPeephole → MulAddFusion → LICM。验证执行顺序正确性和不动点收敛。
- W11：添加 debug 输出（每个 pass 的变更计数、优化前后 IR 对比）。对真实 CNN 模型的 IR 测试优化效果，量化指令减少数。
- W12：撰写文档（5 个 pass 的规则说明、执行顺序原理、添加新 pass 的指南），准备演示。
- W1：学习编译器优化的基本概念：pass、迭代、不动点、use-def 链。阅读龙书第 9 章。阅读现有 5 个 pass 的源码。
- W2：实现统一的 Pass 接口（抽象基类
OptimizationPass）和 PassManager（注册、执行、统计）。支持--opt-level none|basic|all三级配置。 - W3：实现 ConstantFolder 第 1 版：检测 ADD/SUB 的双常量操作数。实现
_compute()方法（支持 float32 和 int32）。 - W4：完善 ConstantFolder：添加 MUL/DIV 支持。实现递归折叠（折叠后的 LOAD_CONST 触发新一轮折叠）。迭代到不动点。
- W5：实现 DeadCodeEliminator：use-def 回溯分析。从 RETURN/STORE/BR 等副作用指令开始标记"活的"指令。实现
_mark_used()的递归遍历。 - W6：完善 DeadCodeEliminator：处理复杂情况（循环内的死代码、跨基本块的 use-def）。迭代到不动点。
- W7：实现 IRPeepholeOptimizer：设计规则表数据结构（模式指令列表 + 替换指令列表）。实现滑动窗口匹配。至少实现 5 条规则。
- W8：实现 MulAddFusion：扫描 mul 指令，检查结果仅被一个 add 使用且无其他使用者。标记 fused_mul_add 属性。
- W9：实现 LICM：FOR/ENDFOR 循环体识别。循环不变量检测（依赖链分析）。安全外提（移到循环前，保持 SSA 正确）。
- W10：测试 Pass 链式执行：ConstantFolder → DeadCodeEliminator → IRPeephole → MulAddFusion → LICM。验证执行顺序正确性和不动点收敛。
- W11：添加 debug 输出（每个 pass 的变更计数、优化前后 IR 对比）。对真实 CNN 模型的 IR 测试优化效果，量化指令减少数。
- W12：撰写文档（5 个 pass 的规则说明、执行顺序原理、添加新 pass 的指南），准备演示。