幂等与不动点:编译器 pass 反复跑的真正含义

从一个 shell 脚本的'幂等'说起——同一个函数反复跑结果不变,这个朴素概念在编译器里有一个精确对应:不动点(fixed point)。本文讲清楚为什么 DCE、常量折叠这种优化 pass 总是写成'loop until no change',以及不动点之外的汇合性、单调性、终止性这几个相关概念。

zT
zTgx
HelloCUDA 站长
2026/06/16 2 周前 799
compileroptimizationpassfixed-pointidempotentdataflow ✓ 已验证
📚 系列 compiler · 第 10 篇

**幂等(idempotency)**这个词出现在系统管理、API 设计、分布式协议等很多领域。在编译器里它有一个特别精确的对应——不动点(fixed point)。本文从一个朴素的 shell 脚本例子出发,讲清楚这两个词是怎么对上的,以及为什么写编译器优化 pass 时几乎逃不掉那个 loop { if !changed { break; } } 模板。

0. 几个名词先说清楚

缩写 / 术语英文中文含义
幂等idempotent幂等同一个操作重复做和做一次,结果一样
不动点fixed point不动点函数 f 的”再做一次也不变”的状态:f(x) = x
不动点迭代fixed point iteration不动点迭代反复应用 f,直到 f(x) == x,常用于优化 pass 跑到收敛
汇合性confluence汇合性 / 合流性不同操作顺序最终到同一个状态(比幂等强)
单调性monotonic单调性信息只能单向增长,保证收敛
终止性termination终止性算法保证能停下来

1. 从一个 shell 脚本说起

先看一个朴素例子,跟编译器无关。

# 装 ch341 驱动 + 禁掉 brltty(它会跟 ch341 抢 USB)
modprobe ch341
systemctl disable --now brltty 2>/dev/null || true

这个脚本是幂等的——跑 1 次还是跑 10 次,最终系统状态都是”ch341 装好 + brltty 禁掉”,不会重复装、不会越跑越乱。

反例(非幂等):

echo "ch341" >> /etc/modules-load.d/ch341.conf

跑 5 次就追加 5 行,系统状态每次都不一样。非幂等。

形式化:

一个操作 f 是幂等的 ⟺ f(f(x)) = f(x)

就是”做完一次再做一次没用”。

2. 编译器里的对应:不动点

在编译器里,每个优化 pass 都可以看作一个函数:

pass : IR → IR

把当前 IR 喂进去,得到优化后的 IR。

幂等的 pass 就是 pass(pass(ir)) = pass(ir)——再跑一次什么都不变。这种 IR 状态叫做这个 pass 的 不动点(fixed point)。

2.1 不动点是个状态,不是个 pass

注意区分:

幂等的 pass这个 pass 本身满足 f(f(x)) = f(x)
不动点状态某个 IR 喂进 pass 得到自己:pass(ir) = ir

两者关系:一个真正幂等的 pass,跑完一次就立刻到不动点。

但很多看起来很常见的 pass 其实不是一次就到不动点的。

3. 为什么 DCE 不能一次跑完

DCE(Dead Code Elimination,死代码消除)的核心规则:

如果一条指令的结果没人用,而且本身无副作用,就删掉它。

看一段简化的 IR:

%v1 = add %a, %b      ; %v1 没人用 → 死,删
%v2 = mul %v1, 2      ; %v2 没人用 → 死,但...等等,删之前 %v1 有人用(就是它)
%v3 = sub %c, %d      ; %v3 没人用 → 死,删

第一遍跑 DCE:

  • %v1 看起来有人用(%v2),不删
  • %v2 没人用,删
  • %v3 没人用,删

跑完得到:

%v1 = add %a, %b      ; 还在

但现在 %v1 突然变成死的了——它原来的唯一用户 %v2 已经被删!

所以要再跑一遍 DCE,这次 %v1 也删掉。第三遍跑发现没东西改了,到达不动点,可以停了。

伪代码:

loop {
    let mut changed = false;
    for op in module {
        if is_dead(op) {
            erase(op);
            changed = true;
        }
    }
    if !changed { break; }      // ← 到不动点
}

这就是为什么编译器优化 pass 几乎都是写成这个模板——它在追”幂等性 / 不动点”。

4. 常量折叠也是同样的故事

常量折叠规则:

add(const a, const b) → const (a + b)

看一段 IR:

%v1 = add 1, 2        ; 都是常量,折成 3
%v2 = add 3, 4        ; 都是常量,折成 7
%v3 = add %v1, %v2    ; 两个操作数原来不是常量,跳过

第一遍折完:

%v1 = const 3
%v2 = const 7
%v3 = add %v1, %v2    ; 现在 %v1 和 %v2 都是常量了,可以折!

第一遍跑漏了 %v3,因为第一遍跑到 %v3 时它的操作数还不是常量。需要第二遍。

第二遍折完:

%v1 = const 3
%v2 = const 7
%v3 = const 10

第三遍跑发现没东西可折,到达不动点。再加上 DCE 把 %v1、%v2 消掉,最后剩 %v3 = const 10。

**这种”前面优化暴露了后面优化的机会”**就是为什么单独看每个 pass 是非幂等的,但 loop until no change 把它们包装成了整体幂等。

5. 不止幂等:三个相关概念

幂等是基础,但只够保证”重复跑没事”。编译器还关心几个更强的性质。

5.1 汇合性(Confluence)

不同顺序应用变换,最终到同一个不动点。

举例:同一段 IR,先跑 DCE 再跑常量折叠,跟先跑常量折叠再跑 DCE,最后得到的 IR 应该一样(至少功能等价)。

汇合性比幂等强——它额外要求”路径无关”。汇合 + 终止 → 唯一最终结果。

LLVM opt -O2 -O2 input.ll 跟 opt -O2 input.ll 结果可能不同,因为 -O2 整个 pipeline 不是汇合的——pass 之间存在相位耦合(phase ordering),换顺序结果就变。这是编译器优化界的著名难题,叫 phase ordering problem(相位排序问题)。

5.2 单调性(Monotonic)

数据流分析的核心性质。

每次迭代,分析得到的”已知信息”只能增长,不能减少。

典型例子:到达定值分析(reaching definitions)——已知”在程序某点 x 可能有哪些值”,这个集合只会越来越大(看到更多路径),不会突然缩小。

为什么单调性重要?单调 + 有限晶格(lattice)→ 保证迭代有限步内收敛到不动点。这是数据流分析能终止的根本原因。

5.3 终止性(Termination)

最朴素的要求:算法必须能停下来。

不动点迭代的 loop until no change 模板,如果不小心写出”删一条 A 又生成一条 B,删 B 又生成 A”的循环操作,就永远停不下来。

终止性通常靠单调性 + 有限晶格保证——既然每轮”信息”只增不减,而总信息量有上限,最多 N 轮就到顶。

6. 实战代码模式

写过编译器 pass 的人会发现自己反复在用这两个模板。

6.1 单 pass 跑到不动点

fn run_pass_to_fixed_point<F>(ir: &mut IR, mut single_pass: F)
where F: FnMut(&mut IR) -> bool   // 返回 true 表示这一轮改动了
{
    while single_pass(ir) {}
}

DCE、常量折叠、代数化简——全是这个模板。

6.2 多个 pass 一起跑到联合不动点

fn run_passes_until_quiescent(ir: &mut IR) {
    loop {
        let mut changed = false;
        changed |= dce(ir);
        changed |= constant_fold(ir);
        changed |= algebraic_simplify(ir);
        if !changed { break; }
    }
}

这个单个 pass 都是非幂等的,但放进 loop !changed,整体表现出幂等性(最终状态稳定)。

LLVM 的 PassManager 实际上有更复杂的调度,但思想是一样的。

7. 反幂等的反例

不是所有”重复跑”都安全。两个常见陷阱:

7.1 副作用的 pass

fn add_logging_to_every_call(ir: &mut IR) {
    for call_op in ir.calls() {
        insert_before(call_op, log_op);    // 加一条 log
    }
}

跑 1 次:每个 call 前面加 1 条 log。 跑 2 次:每个 call 前面加 2 条 log(因为之前加的 log 没被识别成”已经加过”)。

非幂等。要做成幂等需要先检查”是否已经加过 log”。

7.2 命名冲突的 pass

fn rename_temp_to_t<F>(ir: &mut IR) {
    for var in ir.locals() {
        if var.name.starts_with("temp") {
            var.name = format!("t_{}", var.id);
        }
    }
}

跑 1 次:temp_1 → t_5(假设 id=5),OK。 跑 2 次:t_5 已经不以 temp 开头,不变。这个 pass 是幂等的。

但如果改成:

var.name = format!("t_{}", var.name);    // 把原名字嵌进去

跑 1 次:temp_1 → t_temp_1。 跑 2 次:t_temp_1 → t_t_temp_1。 非幂等——每次跑前缀都越长。

写编译器 pass 时,任何”基于当前状态生成新状态”的操作都要警惕——确保第二次跑时输入”看起来不像目标模式”。

8. 一个隐藏的连接:幂等是个通用工程概念

这套概念跨多个领域:

领域”幂等”对应什么
Shell / 系统管理脚本能反复跑不破坏系统
HTTP / RESTGET / PUT / DELETE 是幂等的,POST 不是
分布式系统消息重传,接收方不会重复执行
数据库UPSERT,INSERT … ON CONFLICT
编译器优化 pass跑到不动点,这一篇讲的事
函数式编程纯函数 + 不可变数据,自然幂等
容器 / Kubernetes 声明式配置状态收敛,跑 reconcile loop 到不动点

理解编译器里的不动点会让你顺手理解 Kubernetes 的 controller loop——它就是 reconcile pass 跑到不动点。一通百通。

9. 一句话总结

编译器里的”不动点”就是 shell 脚本里的”幂等”——再跑一次状态不变。但因为很多优化 pass(DCE、常量折叠、代数化简)单独跑是非幂等的(前面优化暴露后面机会),实战中写成 loop { if !changed { break; } } 把它们包装成整体幂等。这个 loop until no change 模板背后是编译器迭代式优化的核心:不动点迭代。再加上单调性保证收敛、汇合性保证路径无关,就是编译器优化为什么能既正确又能停下来的全部秘密。

系列上一篇: 编译器优化 pass 速查表:30 个名字背后的概念

评论区
评论功能即将上线, 敬请期待。