图优化：公共子表达式消除

可视化演示

展示CSE合并计算图中重复子表达式的前后对比、值编号等价检测机制、局部CSE与全局CSE(GVN)的作用范围差异，交互切换核心环节。

1. 问题与动机

后厨主管看了一会儿就发现了问题：两位厨师都在切葱花、切蒜末、调糖醋汁，动作完全一样，但谁也没想到向对方要一份。鱼香肉丝和宫保鸡丁口味不同，可它们共享的备菜步骤是相同的。与其各做各的，不如让备菜中心统一完成一次，再分给两个灶台。这个直觉，正是公共子表达式消除的出发点。

到了 AI 模型的世界，类似场景每天都在发生。一个模型的前向流程里，可能有多个分支都需要计算某个中间张量，比如 a + b。如果编译器没有注意到这两个 a + b 其实是同一个计算，它就会在 GPU 上老老实实执行两次。浪费的不只是算力，还有中间结果的存储开销和访存带宽。用后厨的话说，这就是同一份糖醋汁被熬了两遍。

CSE 的做法很朴素：一旦发现某个子表达式已经计算过，并且后面的计算需要的输入来源完全相同，就不再重复计算，而是直接复用上一次的结果。假设这个子表达式被使用 \(k\) 次，消除前后的总成本可以写成：

回到后厨，主管并没有改变菜谱，只是把“切葱、切蒜、调汁”这份备菜从重复劳动变成了公共资源。CSE 同样不改算子的数学含义，它只是让相同的中间结果不再被重复制造。理解了这一点，后面的图视角和算法细节就都好懂了。

2. 计算图视角

后厨主管为了看清楚整个流程，把每道菜的做法画成了一张流程图：一个方框代表一个动作，一条箭头代表半成品从一个动作流向另一个动作。鱼香肉丝和宫保鸡丁的流程图虽然终点不同，但前面一段“爆香葱蒜、调糖醋汁”被画了两遍。他一眼就看出，这是同一张子图。

AI 编译器也用类似的方式理解模型。这种图叫计算图：节点是算子，比如加法、卷积、矩阵乘法；边是张量，也就是算子的输入和输出。模型前向时，数据沿着边流动，每经过一个节点就完成一次计算。如果两张流程图的局部出现完全相同的节点组合，编译器就会看到一个“重复的子图”。

识别重复子图，本质上是在比较结构是否等价。对任意一个节点 \(n\)，它的子结构可以递归地写成：

用流程图来思考，CSE 的“公共”二字就很清楚了：它不只是两个节点长得像，而是从输入一路到输出，整棵子树的结构和算子类型都一致。只有这样的两份备菜，才真正可以放心共用。

3. 核心识别思想

主管要给备菜中心定规则：怎样判断两份备菜是否相同？他每道工序都写成一个签名，比如“3 毫米葱花 + 5 克蒜末 + 200 毫升高汤”。只要签名一样，就认为这道备菜可以共享。这个签名并不关心是谁切的、用什么刀切的，只关心工序本身。

编译器里的 CSE 同样会为每个节点生成签名。它的做法是从计算图底部向上遍历：先处理输入节点，再处理它们的父算子。这样当某个算子需要比较时，它的输入签名已经准备好了。签名由算子类型和输入签名共同组成：

其实这就像后厨给“糖醋汁”定了一个标准编码：以后不需要每次现场拿鼻子闻、拿舌头尝，只要看到相同编码，就知道它是同一份备菜。CSE 的核心识别思想，就是给计算图中的每个子表达式生成这样的标准编码。

4. 哈希值编号

后厨的备菜越来越多，主管不能每次都把两份备菜的原料摊开对比。他开始给每类备菜分配编号：糖醋汁是 7 号，葱蒜末是 3 号。后厨墙上挂着一张表，从签名查到编号，再顺着编号找到备菜本身。这样一来，新来的备菜只需看一眼签名，就知道是不是重复的。

编译器里的 CSE 也维护了一张类似的大表，叫“全局值编号表”。它把哈希签名映射到一个唯一编号，再用编号代表对应的中间值。查表过程可以写成：

哈希的好处是快，但哈希也有代价：两个不同表达式可能撞出同一个签名。所以真正严谨的编译器在哈希命中后，还会做一次结构化等价确认，就像两个备菜编码相同时，再抽查一下原料有没有细微差别。哈希值编号让 CSE 在海量节点中依然能保持高效。

5. 收益与代价

中央厨房并不是免费的。主管要维护备菜表、设置备菜中心、安排专人登记编号，这些都要成本。更重要的是，有些备菜做出来之后如果没人立刻取走，就要放在冰箱里占地方。共享一个中间结果，有时会让这个结果存活更长时间，反而增加内存压力。

CPU 和 GPU 上也有类似现象。CSE 减少了重复计算，但被共享的中间值可能被多个下游消费者引用，生命周期变长，寄存器或缓存压力随之上升。编译器必须估算收益，不能无脑合并。假设单次子表达式成本是 \(C_{\mathrm{sub}}\)，哈希维护成本是 \(O_{\mathrm{hash}}\)，那么优化净收益大约是：

所以 CSE 不是“越合并越赚”。当重复次数很多、单次计算又昂贵时，它是大赢家；当重复次数只有一次、哈希开销却很大时，主管就该按兵不动。真正优秀的编译器不是机械地套公式，而是像经验丰富的后厨主管一样，先估算再动手。

6. 编译栈落地

连锁餐厅规模扩大后，主管把“识别重复备菜”的规则写成了软件，装进每家分店的厨房系统里。AI 世界也一样，像 XLA 和 PyTorch 2.0 的编译栈，已经把 CSE 做成了标准优化流程中的一个固定环节。模型在前端描述出来后，编译器会把它翻译成中间计算图，再经过一系列优化 pass，CSE 就是其中一员。

在 XLA 中，CSE 经常作用于 HLO（High Level Optimizer）层的计算图；在 PyTorch 2.0 的 torch.compile 路径里，类似思想也出现在图优化和代码生成阶段。它常常和 DCE（死代码消除）配合使用：CSE 负责把重复计算合并成一次，DCE 负责清理合并后已经没人使用的旧节点。整个流程可以写成：

对做部署的工程师来说，看到推理时 GPU 利用率不高、显存占用偏高，除了看算子实现，也要怀疑是不是图里存在重复计算。CSE 就像后厨系统里的自动备菜模块：它不会改变菜的味道，但会让整个厨房少一些没必要的烟火气。

AI 应用场景

Python 演示

def cse(program):    value_table = {}    var_to_num = {}    num_to_name = {}    result = []     def resolve(src):        if src in var_to_num:            return num_to_name[var_to_num[src]]        return src     for op, dst, src1, src2 in program:        lhs = resolve(src1)        rhs = resolve(src2)        signature = (op, lhs, rhs)         if signature in value_table:            old_num = value_table[signature]            old_name = num_to_name[old_num]            result.append(("copy", dst, old_name))            new_num = old_num        else:            new_num = len(num_to_name)            value_table[signature] = new_num            num_to_name[new_num] = dst            result.append((op, dst, src1, src2))         var_to_num[dst] = new_num     return result  if __name__ == "__main__":    program = [        ("add", "t0", "a", "b"),        ("mul", "t1", "t0", "c"),        ("add", "t2", "a", "b"),        ("mul", "t3", "t2", "d"),    ]    optimized = cse(program)    for ins in optimized:        print(ins)

1. def resolve(src):把历史赋值替换成最初的变量名，保证比较时用的是规范名字。
2. signature = (op, lhs, rhs)用算子和两个操作数组成“备菜签名”。
3. if signature in value_table:如果签名已经见过，说明这是重复的子表达式。
4. result.append(("copy", dst, old_name))新变量只需复制之前的结果，不必重新计算。
5. num_to_name[new_num] = dst给新表达式分配一个编号，并记住编号对应的变量名。
6. var_to_num[dst] = new_num记录当前变量的编号，供后续指令继续追踪。

常见误区

面试题