课题13：窥孔优化器

难度：低 | 类型：项目实战 | 源文件：scratchv/backend/asm_peephole.py | 行数：~400 状态：✅ 已完成

概述

在生成的RISC-V汇编代码上，匹配并替换低效指令序列（如连续加法、冗余移动等），减少指令数。

---

理解背景

是什么？

窥孔优化器（Peephole Optimizer）在汇编层面做"局部小手术"——用一个滑动窗口扫描汇编代码，匹配到某些低效指令组合后，替换为更高效的等价指令（或直接删除）。

名字由来：就像通过门上的"窥孔"看东西，每次只看很小的范围（2-3 条指令）。

为什么？

编译器的代码生成通常是机械化的"模板翻译"，会产生一些显然低效的指令组合。例如：

# 代码生成器可能产生：
li a0, 5          # a0 = 5
addi a0, a0, 3    # a0 = a0 + 3

# 窥孔优化后：
li a0, 8          # a0 = 8 （常量折叠）

这类优化在汇编层面做最合适——因为所有指令都已经"展开"了，模式匹配最直接。

核心概念

1. 优化规则（PeepholeRule）

每条规则有三要素：

PeepholeRule(
    name="addi+addi fusion",           # 规则名称
    pattern=["addi", "addi"],           # 匹配模式（2条连续的 addi）
    replacement=["addi {rd} {rs1} {imm_sum}"],  # 替换为 1 条
    register_constraints=[...],         # 寄存器约束：rd 必须相同
)

2. 5 条默认规则

规则	匹配	替换	效果
addi+addi fusion	addi x,a,N; addi x,x,M	addi x,a,N+M	两条合并为一条
redundant mv swap	mv x,y; mv y,x	删除	无意义的交换
li+addi fusion	li x,N; addi x,x,M	li x,N+M	常量折叠
beq zero-zero to j	beq x0,x0,label	j label	无条件跳转简化
redundant mv elimination	mv a,b; ... mv c,a	mv c,b	跳过中间寄存器

3. 固定点迭代

优化器会反复扫描直到没有新变化（fixed point）：

原始汇编 → 扫描 → 匹配 → 替换 → 新汇编
                                    ↓
                          有变化？──是→ 再扫描
                              ↓否
                           输出最终汇编

最多迭代 50 轮（防止无限循环）。

---

详细任务

1. 定义3~5个窥孔优化规则，例如：
2. addi x1, x1, 1; addi x1, x1, 1 → addi x1, x1, 2
3. mv x1, x2; mv x2, x1 → 删除两条（如果可交换）
4. li x1, 0; addi x1, x1, 1 → li x1, 1
5. beq x0, x0, label → 无条件跳转j label
6. 编写汇编解析器，将每行解析为对象（标签、操作码、操作数列表）。
7. 实现滑动窗口扫描，匹配规则并替换，迭代直到不动点。
8. 输出优化后的汇编，并统计匹配次数和节省的指令数。
9. 集成到编译器后端，添加--peephole开关。

---

交付产物

• 独立的peephole.py脚本或集成模块
• 测试汇编文件及优化前后对比
• 文档：规则列表、使用方法

---

代码走读

基本使用

from scratchv.backend.asm_peephole import AsmPeepholeOptimizer

asm_text = """
main:
    li a0, 5
    addi a0, a0, 3
    beq x0, x0, .L1
.L1:
    ret
"""

opt = AsmPeepholeOptimizer()
optimized, changes = opt.optimize(asm_text)
print(optimized)
print(f"Changes made: {changes}")
print(opt.report())

从命令行使用

# 优化汇编文件
python -m scratchv.backend.asm_peephole output.s -o optimized.s --report

# 列出所有可用规则
python -m scratchv.backend.asm_peephole --list-rules

自定义规则

from scratchv.backend.asm_peephole import PeepholeRule, AsmPeepholeOptimizer

# 自定义规则：连续的 nop 删除
my_rules = [
    PeepholeRule(
        name="nop elimination",
        pattern=["nop"],
        replacement=[],  # 空 = 删除
        register_constraints=[],
    ),
]

opt = AsmPeepholeOptimizer(rules=my_rules)

核心循环

def optimize(self, asm_text):
    lines = _parse_asm(asm_text)  # 解析为 AsmLine 列表
    total_changes = 0

    changed = True
    iteration = 0
    while changed and iteration < 50:
        changed = False
        iteration += 1
        new_lines = []
        i = 0

        while i < len(lines):
            matched = False
            for rule in self.rules:
                window = lines[i:i + len(rule.pattern)]
                bindings = _match_rule(rule, window)  # 尝试匹配
                if bindings is not None:
                    # 匹配成功！应用替换
                    new_lines.extend(self._apply_replacement(...))
                    i += len(rule.pattern)  # 跳过匹配的指令
                    matched = True
                    changed = True
                    break

            if not matched:
                new_lines.append(lines[i])  # 保留原指令
                i += 1

        lines = new_lines

    return _lines_to_asm(lines), total_changes

模式匹配

def _match_rule(rule, window):
    bindings = {}
    for i, (pat_op, line) in enumerate(zip(rule.pattern, window)):
        # 匹配操作码
        if pat_op != "*" and pat_op != line.opcode:
            return None
        # 匹配操作数，记录寄存器绑定
        for j, actual in enumerate(line.operands):
            if not _operand_matches(expected_ops[j], actual, bindings):
                return None
    # 检查跨指令的寄存器约束
    return bindings

---

动手练习

练习 1: 观察优化效果

写一段包含冗余指令的汇编（比如 li + addi），用窥孔优化器处理，对比前后的变化。

练习 2: 添加新规则

设计一条新规则。比如： - 连续的 mv a, b; mv b, c → mv a, c - addi x, x, 0 → 删除（加 0 无意义）

练习 3: 分析 CNN 模型的优化机会

对 CNN 模型生成的汇编运行窥孔优化器，看有多少指令被优化掉了。

---

常见坑

坑	说明
寄存器别名	x0 和 zero 是同一个寄存器，但字符串比较不相等。需要做规范化
规则顺序	规则的应用顺序影响最终结果——可能规则 A 的替换产物正好被规则 B 匹配
常量折叠的溢出	addi+addi fusion 中两个立即数相加可能超出 12 位有符号范围（-2048~2047），需要检查
固定点不一定最优	当前的贪心匹配（遇到第一条匹配的规则就应用）可能不是全局最优的规则应用顺序

---

进阶阅读

• 龙书（Compilers: Principles, Techniques, and Tools）第 8.5 节：Peephole Optimization
• LLVM 的窥孔优化：TableGen Peephole Patterns
• 相关课题: 课题5 — 汇编代码美化器 | 课题14 — 常量加载合并优化 | 课题18 — 指令调度

---

12周每周目标

• W1：学习窥孔优化原理，收集常见低效汇编模式。
• W2：设计规则表（每条规则包含模式指令列表和替换指令列表）。
• W3：编写汇编加载函数，将每行解析为对象（操作码、操作数等），保留原始字符串。
• W4：实现模式匹配：滑动窗口大小等于规则长度，比较操作码和操作数（支持通配符如任意寄存器）。
• W5：实现替换：删除匹配窗口，插入新指令列表，重新扫描。
• W6：实现第一条规则：addi x1,x1,1; addi x1,x1,1 → addi x1,x1,2。测试。
• W7：实现规则：mv x1, x2; mv x2, x1 → 删除两条（简单情况）。
• W8：实现规则：li x1, 0; addi x1, x1, 1 → li x1, 1。
• W9：实现规则：beq x0, x0, label → j label（需要处理标签）。
• W10：增加优化报告，打印匹配次数、节省的指令数。
• W11：集成到编译器后端（在汇编生成后自动调用），添加--peephole开关。
• W12：测试10个以上汇编文件，用模拟器验证正确性，撰写文档。