4、常量传播与折叠：常量传播算法、条件常量传播、稀疏条件常量传播

聊到图优化，常量传播与折叠绝对是个绕不开的基础话题。我刚开始接触编译器时，觉得这玩意儿不就是把常量算出来嘛，有啥好讲的？后来真正动手做神经网络编译器，才发现这里面的门道比想象中深得多。

说白了，常量传播就是让常量值在计算图里"跑起来"。比如一个节点的输出是 3，那所有用到这个输出的节点，都可以直接用 3 替换掉对应的变量引用。而常量折叠更直接——既然你全是常量，那我干脆把计算结果算出来，省得运行时再折腾。

4.1 常量传播算法

最基本的常量传播算法，其实就是一个数据流分析问题。我习惯把它理解成"给每个变量贴标签"的过程。每个变量有三种状态：

• 未定义：还没分析到，或者值不确定
• 常量：确定是一个固定值，比如 5
• 非常量：这变量没法确定，可能是动态输入的

算法怎么跑？从图的入口开始，沿着数据依赖关系往下推。遇到常量赋值，就把这个常量值传播到所有使用它的地方。遇到运算节点，如果所有输入都是常量，那就直接计算结果，把结果也标记成常量。

举个简单的例子：

// 原始代码
a = 2
b = 3
c = a + b
d = c * 4
e = d + 1

// 常量传播+折叠后
a = 2
b = 3
c = 5      // 2+3 折叠了
d = 20     // 5*4 折叠了
e = 21     // 20+1 折叠了

嗯，这里要注意：如果图里有循环，那算法就得小心了。我曾经在项目里遇到过一个循环内的常量传播，第一次迭代时变量还是常量，第二次迭代就变了。这种情况需要做 widening（放宽处理），直接把变量标记为非常量，避免死循环。

4.2 条件常量传播

基本的常量传播有个明显的短板——它不考虑控制流。你想想看，一个 if 分支里的变量，在某个分支上可能是常量，在另一个分支上可能不是。传统算法会直接取并集，结果就是两边都变成非常量。

条件常量传播（Conditional Constant Propagation）就是来解决这个问题的。它把控制流信息也纳入分析范围。说白了，就是"我知道你走哪条路，我就按哪条路的值来算"。

算法怎么做？它维护两个格子：

• 值格（Value Lattice）：记录每个变量的常量状态
• 执行格（Executable Lattice）：记录每个边/节点是否可达

两个格子互相影响。只有可达的节点才参与常量传播，不可达的节点直接忽略。这样就能避免"把两个分支的值混在一起"的问题。

举个例子：

if (condition) {
    x = 5
} else {
    x = get_dynamic_value()
}
y = x + 3

传统常量传播会认为 x 可能是 5 也可能是动态值，所以 y 没法折叠。但条件常量传播会分析：如果 condition 本身是常量（比如 True），那 else 分支根本不会执行，x 就是 5，y 就是 8。

4.3 稀疏条件常量传播

条件常量传播虽然好，但有个性能问题——它太"密"了。什么意思？就是它需要分析图里的每一个节点和每一条边。对于大型神经网络，计算图可能有几万个节点，全量分析的成本很高。

稀疏条件常量传播（Sparse Conditional Constant Propagation，简称SCCP）就是优化版本。它的核心思想是：只分析那些"可能发生变化"的变量。

我记得第一次在论文里看到SCCP时，觉得这名字起得真好。"稀疏"两个字点出了本质——大部分变量其实不会因为常量传播而改变状态，我们没必要在它们身上浪费算力。

算法流程大致如下：

1. 把图转换成SSA形式
2. 初始化所有变量的状态为"未定义"
3. 维护一个工作列表，只放入那些"输入状态发生变化"的节点
4. 从工作列表中取出节点，重新计算它的输出状态
5. 如果输出状态变了，就把所有使用这个输出的节点加入工作列表
6. 重复直到工作列表为空

这样做的好处很明显：

• 不需要遍历所有节点，只处理"有动静"的节点
• 收敛速度快，因为大部分节点只处理一次
• 内存占用低，不需要维护全图的格子状态

4.4 三种算法的对比

我把这三种算法的特点整理了一下，方便你对比：

算法	考虑控制流	分析粒度	适用场景	复杂度
基本常量传播	否	全量	简单线性计算图	O(N)
条件常量传播	是	全量	有分支的图	O(N*E)
稀疏条件常量传播	是	稀疏	大型复杂图	O(N log N)

在实际的神经网络编译器中，我个人更倾向于使用SCCP。原因很简单——神经网络的图通常很大，而且有很多重复结构（比如同一个算子在不同层重复出现）。SCCP的稀疏特性正好能应对这种场景。

4.5 知识体系图

下面这张图展示了常量传播与折叠的整体知识结构：

从这张图可以看出来，三种算法其实是一个逐步演进的过程。基本常量传播是基础，条件常量传播加了控制流分析，SCCP又在这个基础上做了稀疏化优化。在实际工程中，我建议你直接从SCCP入手，因为它的性价比最高——实现复杂度适中，但效果远好于前两者。

---