想象一家大型中央厨房：客人点的是“糖醋排骨”，但后厨真正执行的是一张张动作卡片——“切块”“腌制”“油炸”“裹汁”。编译器也一样，它不会直接让 CPU 去做“糖醋排骨”，而是先把源码翻译成一张张只含一个动作的卡片，这就是三地址码。后来厨房搞了场改革：每只装食材的容器只能用一次，新食材必须换新容器，这就是 SSA 的单赋值。遇到两条流水线汇合，就用一个 φ 分拣闸决定选用哪边的食材。本文会用这座厨房带你走完从三地址码到 SSA 构造、再到回归普通代码的完整旅程。
理解三地址码与 SSA，是看懂 LLVM、TVM 等现代编译/推理框架优化流程的钥匙；对 AI 编译器工程师来说，这决定了你能否把模型高效地“炒熟”成可运行的机器码。
可视化演示
展示三地址码指令格式、SSA构造与phi函数插入及支配者树与支配边界，支持变量版本调节。
本节配有交互动效（进入视口后自动加载，约 3KB）。
三地址码指令格式 紫色赋值指令x=y op z，每条指令最多三个操作数 黄色控制流指令if x relop y goto L实现条件跳转 x = y op z | x = op y | goto L 三地址码简洁统一，易于生成和优化
三地址码基础
想象中央厨房接到“糖醋排骨”的订单。大厨不会把整道菜丢给一个人，而是拆成“切块、腌制、挂糊、油炸、裹汁、装盘”一张张动作卡片。编译器也一样：前端解析完源码后，先产生一种扁平的过渡语言——三地址码，让每一张卡片只记录一个最小动作。
三地址码的指令形式很固定：x = y op z。其中 op 可以是加减乘除、比较、跳转、函数调用等；y 和 z 是源操作数，x 是放结果的新位置。这里的“地址”不一定是内存地址，可以理解成一个个编号的食材容器（变量或临时变量）。每条指令最多涉及三个地址，所以叫三地址码。
四元组表示把一条三地址码写成四个字段：(op, y, z, x)。例如 t1 = a + b 写作 (+, a, b, t1)。临时变量 t1、t2 就像厨房里编号的一次性餐盒，每个中间结果都有自己的名字，避免把一锅菜反复倒进同一个碗里。
AST 是一棵大树，三地址码则像被压平的卡片。每张卡片动作单一、字段清晰，后续优化和代码生成都像厨师按卡片顺序接力，不用再爬一遍语法树。
- 操作码 op
\mathrm{op}代表动作，例如+、-、*、跳转。 - 第一源操作数 y第一个参与动作的原料/地址。
- 第二源操作数 z第二个原料/地址；一元操作时通常为空。
- 目标 x把动作结果写到
x指向的容器，通常是一个全新编号的临时变量。
控制流图CFG
卡片一多，厨房就需要一张工序流程图。控制流图（CFG）把连续执行、中间没有分支的卡片合成“基本块”，块与块之间用有向边连接。边代表“做完这一堆卡片后，下一步可能走到哪一堆卡片”。
基本块的划分规则很简单：程序入口、跳转目标、跳转指令的下一条指令都是“带头卡片”。从带头卡片开始，不断加入后续语句，直到遇到跳转指令或下一个带头卡片为止。基本块内部是直线执行，不能从中间进入，也不能从中间离开。
CFG 是数据流分析的地图。每个基本块的入口和出口都是“程序点”，SSA 的 φ 函数就插在块入口这个程序点上。跳转连接则把不同卡片堆串成一条条可走的路径，编译器在后端算法中频繁在这些路径上做推理。
有了 CFG，后续的支配关系和 SSA 构造就有了统一地图。厨房里的每一条“出菜路线”都在这张图上，哪里可能汇合、哪里必须设分拣闸，一目了然。
- V 基本块集合\(V = \{B_1,\ldots,B_n\}\) 是所有卡片堆的集合。
- E 有向边集合\(E\) 中的每条边 \( (B_i,B_j) \) 表示块 \(B_i\) 执行后可能进入块 \(B_j\)。
- next(Bi)=Bj表示块 \(B_i\) 末尾没有跳转，自然落入 \(B_j\)。
- jump(Bi)=Bj表示块 \(B_i\) 末尾的跳转指令把控制流交给 \(B_j\)。
单赋值与phi
SSA 是一场“容器只用一次”的改革。普通代码里，变量像抽屉，可以反复拉开换内容；SSA 中每个变量名只能被赋值一次。如果同一逻辑变量要多次赋值，就生成 x1、x2、x3 这样带编号的新名字。每个新名字只有一个定义点，数据流动路径极其清晰。
问题来了：if 的两个分支分别给 x 赋了不同的值，汇合之后到底用哪个？传统代码用同一个抽屉覆盖，SSA 不能覆盖，所以需要 φ 函数。φ 是编译中间表示里的一种特殊“分拣闸”：它根据控制流实际来自哪个前驱块，选择对应编号的值。
单赋值让每个名字只有一个定义点，所以常量传播、死代码消除等优化变得非常简单：想知道某个值从哪来，只要找到这个名字的唯一定义即可。厨房里每份食材都有唯一“溯源码”，出了质量问题能立刻定位是哪条线、哪只容器。
x3 等于 x1；如果从第二个分支过来，x3 等于 x2。- 目标 x3
x_3是汇合后使用的新版本变量，由 φ 选出。 - φ 标记
\phi不是普通函数调用，而是表示“按前驱选择”。 - x1 来源一
x_1是第一个前驱块里对x的赋值。 - x2 来源二
x_2是第二个前驱块里对x的赋值。
支配者关系
SSA 的 φ 不是随便插的，它需要插在“必经之路”的边界上，所以必须先算支配关系。在 CFG 中，如果从入口到某个基本块 n 的所有路径都经过 d，就说 d 支配 n。这就像厨房送餐：不管客人走哪条走廊，都要经过检查站 d，d 才能支配终点 n。
在支配关系之上可以建立支配者树：每个节点只保留离自己最近的支配者（直接支配者）作为父节点。这棵树浓缩了 CFG 的最重要控制骨架，编译器可以在树上快速判断“谁管着谁”。
支配边界则回答“某个检查站的控制力到哪里结束”。如果 d 支配 m 的某个前驱，但 d 并不严格支配 m，那么 m 就在 d 的支配边界内。这里的“严格支配”指 d 支配 m 且 d ≠ m。φ 函数正是要插在这些支配边界对应的基本块里。
- Pred(m)
\mathrm{Pred}(m)是m的所有直接前驱块集合。 - ∃ p至少存在一个前驱
p满足条件。 - n dom p
n支配前驱p，说明n的影响力已经覆盖到m门口。 - ¬(n sdom m)
n不严格支配m，说明这种影响力在m处第一次没能“说了算”，所以m需要分拣闸。
SSA构造算法
SSA 构造像在厨房里全面安装“溯源码系统”，分三步：先算出每个节点的支配边界，再在需要汇合的地方插入 φ，最后给所有变量做深度优先重命名。第一步确定分拣闸装在哪，第二步装闸，第三步给每份食材贴上唯一编号。
插入 φ 的位置可以这样算：对变量 v，收集所有定义 v 的基本块，把这些块各自的支配边界全部取并集，得到的节点就是要插入 φ 的地方。注意这不是一次就能完成的，因为新插入的 φ 本身也是一个“定义”，它又可能在新的支配边界产生更多 φ，所以要反复迭代到不动点。
插完 φ 后，还要重命名变量：深度优先遍历支配者树，维护每个变量当前版本号。遇到一个定义就生成新名字 v_i，遇到一个使用就替换成当前栈顶版本。这样，每个变量名都只有一个定义点，SSA 正式建成。LLVM 的 mem2reg pass 做的核心工作之一，就是把普通内存读写提升成这种 SSA 寄存器形式。
v 需要插 φ 的位置，等于它所有定义点支配边界的并集。- Defs(v)
\mathrm{Defs}(v)是所有给变量v赋值的块集合。 - DF(b)
\mathrm{DF}(b)是块b的支配边界。 - ⋃ 并集把所有边界点合并，得到首批 φ 候选位置。
- 迭代语义新插入的 φ 会继续参与并集计算，直到不再产生新 φ。
SSA析构与LLVM
优化做完之后，CPU 并不认识 φ。SSA 析构就是把 φ 拆掉，回到普通三地址码。这相当于厨房优化完流程后，把分拣闸撤掉，改成在每个前驱工作台提前把对应食材送到汇合口。
基本做法是：对每个 φ 指令 x = φ(x1, x2)，在第一个前驱块末尾插入 x = x1，在第二个前驱块末尾插入 x = x2，然后删除 φ。多个 φ 同时存在时，它们可能构成“并行拷贝”——像同时交换两杯水，必须借助临时容器拆成顺序拷贝，否则会互相覆盖。
LLVM 的 IR 正是这种工业级三地址码风格：% 开头的虚拟寄存器、phi 指令、基本块标签一应俱全。优化 pass 在 SSA 上做常量传播、循环不变式外提、死代码消除，后端再通过 SSA 析构和寄存器分配把逻辑变成机器码。可以说，LLVM 的优化能力一半来自这套类似“中央厨房改革”的 SSA 骨架。
- B1 前驱拷贝在 \(B_1\) 块末尾写入
x = x1，模拟从第一个分支来的情况。 - B2 前驱拷贝在 \(B_2\) 块末尾写入
x = x2，模拟从第二个分支来的情况。 - remove φ原来的
x = φ(x1,x2)使命完成，可以删除。 - 并行拷贝多个 φ 同时存在时，需要临时变量做并行交换。
AI 应用场景
深度学习编译器中的算子融合
阶段：模型编译优化阶段
解决的问题：传统推理引擎按图逐个执行算子，中间张量不断写回显存再读出来，访存开销巨大。AI 编译器先把算子图翻译成三地址码风格的 IR，再用 SSA 单赋值让每个中间张量只有一个定义点，后端就能安全判断哪些算子可以融合、哪些中间结果可以复用内存。
具体案例：TVM/MLIR 把 ONNX 或 PyTorch 图翻译成 MLIR/TIR，优化 pass 在 SSA 信息指导下做算子融合和 buffer 复用，最后交给 LLVM 处理寄存器级优化。
大模型推理引擎的常量折叠
阶段：图优化与预计算阶段
解决的问题：大模型推理里有些 shape 推导、mask 生成、位置编码结果在运行时完全不变，但每次请求都重复计算。SSA 的“单赋值”让每个值只有一个来源，常量传播 pass 可以沿着定义链一路折叠，把死代码直接删掉，减少推理延迟。
具体案例：TensorRT 和 FasterTransformer 在引擎构建期做常量折叠与死代码消除，批量推理时省掉大量冗余 kernel launch。
静态程序分析与安全审计
阶段：代码数据流分析阶段
解决的问题：安全工具需要追踪用户输入是否流到了危险函数，也就是“污点传播”。SSA 中每个变量只有一个定义点，数据流路径天然显式，分析器可以像顺着厨房的溯源码追查食材来源一样，快速定位污染源。
具体案例：LLVM 的 DataFlowSanitizer 和许多静态分析器都基于 SSA 形式做污点分析，辅助发现 SQL 注入、内存越界等漏洞。
Python 演示
# 简易 SSA 构造 demo: 给定 CFG 前驱图, 计算支配关系与支配边界, 并插入 phifrom collections import defaultdict preds = { 0: [], 1: [0], 2: [0], 3: [1, 2], 4: [3, 0],} def build_dom(preds, entry=0): nodes = set(preds) dom = {n: set(nodes) for n in nodes} dom[entry] = {entry} changed = True while changed: changed = False for n in nodes: if n == entry: continue new = set.intersection(*(dom[p] for p in preds[n])) | {n} if new != dom[n]: dom[n] = new changed = True return dom def build_df(preds, dom): df = defaultdict(set) nodes = set(preds) for b in nodes: for p in preds[b]: # 若 d 支配前驱 p, 且 d 不严格支配 b, 则 b 在 DF(d) 中 for d in dom[p]: if d == b or d not in dom[b]: df[d].add(b) return df def insert_phi(def_blocks, df): phi_blocks = set() work = set(def_blocks) while work: n = work.pop() for b in df[n]: if b not in phi_blocks: phi_blocks.add(b) work.add(b) return phi_blocks if __name__ == "__main__": dom = build_dom(preds) df = build_df(preds, dom) phi = insert_phi([1, 2], df) for node in sorted(preds): print("block", node, "dom", sorted(dom[node]), "df", sorted(df[node])) print("phi blocks:", sorted(phi))
new = set.intersection(*(dom[p] for p in preds[n])) | {n}一个块的新支配者是所有前驱支配者的交集再加上自己。if d == b or d not in dom[b]:如果d支配某个前驱但没有严格支配b，b就是d的支配边界。work.add(b)新插入的 phi 本身也是一个“定义”，要把b继续放进工作列表传播 phi。
常见误区
误区三地址码和汇编都是“一条条指令”，那它俩应该差不多，反正最后都要变成机器码。
正解三地址码是机器无关的中间表示，变量和临时变量由编译器管理，不绑定具体寄存器或内存寻址方式；汇编则是针对目标 CPU 的文本形式，指令集和寄存器都固定。厨房里的“切块”卡片是通用动作，具体用哪把刀、哪块砧板是后端的事。
为何常见：两者都是线性指令序列，外形相似，初学者很容易把“中间表示”和“目标汇编”混为一谈。
误区SSA 要求每个变量只能赋值一次，所以写代码时不能出现 `x = x + 1` 这种语句。
正解SSA 确实要求每个变量名只有一个定义点，但这是靠重命名实现的。源码里的 x 第二次赋值会变成 x1，第三次变成 x2，汇合时再用 φ(x1,x2) 合并。容器每个只能用一次，但仓库里有源源不断的新容器。
为何常见：“单赋值”这个名称太有误导性，让人以为是在限制程序员写代码，其实它是中间表示内部的重命名规则。
误区φ 带了函数名，肯定会在运行时被调用，会有栈帧和调用开销。
正解φ 是编译期/IR 层的特殊指令，它表示“按前驱块选择值”，不产生函数调用，也不需要栈帧。SSA 析构阶段会把它转成普通拷贝或直接消除。分拣闸是静态布置的，不是每个包裹现场打电话问路。
为何常见：名字里带“函数”两个字，加上很多资料直接用 phi(x,y) 形式书写，很容易误解成运行时函数。
误区只要两个分支汇合了，就到了支配边界，就得插 φ。
正解支配边界 DF(d) 是 d 的控制力边界，要求 d 支配某个前驱但不严格支配目标块。不是所有汇合点都在 d 的支配边界里。每个检查站只在自己的势力范围边缘设卡，而不是在整栋楼每个门口都设卡。
为何常见：φ 经常出现在汇合点，初学者容易把“需要 φ 的位置”直接等同于“所有汇合点”。
面试题
Q1. 三地址码最典型的指令形式是？
- A.
x = y op z← 正确答案 - B.
mov eax, [x] - C.
int f() { return 1; } - D.
#define
答案：A。三地址码是机器无关的中间表示，核心形式就是 x = y op z，一条指令最多三个地址。mov eax 是目标汇编，函数源码和宏定义都是更高层的源码形式。
Q2. 四元组 (op, y, z, x) 中，哪个字段是结果？
- A.
op - B.
y - C.
z - D.
x← 正确答案
答案：D。四元组的惯例是“操作码、源操作数1、源操作数2、目标结果”。x 是结果字段，y 和 z 是参与运算的源操作数。
Q3. 在 CFG 中，基本块是指？
- A.只有一个跳转指令的块
- B.只能从第一条进入、最后一条离开，中间没有跳转的直线语句序列← 正确答案
- C.不包含任何变量的语句集合
- D.所有跳转目标的集合
答案：B。基本块是直线执行的语句序列，入口不能从中间进入，出口不能从中间离开，块内没有分支或跳转目标。它像一叠连续动作的工序卡片，整叠执行。
Q4. SSA 的“单赋值”核心含义是？
- A.每个变量名只有一个定义点← 正确答案
- B.每个基本块只能有一条赋值指令
- C.所有赋值只能放在入口块
- D.每个 phi 只能有一个参数
答案：A。SSA 不是说整个程序只能赋一次值，而是通过重命名让每个变量名只有一个定义点。同一逻辑变量多次赋值会变成 x1、x2，再用 φ 合并。
Q5. x3 = phi(x1, x2) 出现在基本块入口，其语义是？
- A.取 x1 和 x2 中较大的一个
- B.运行时调用函数 phi 求值
- C.根据实际到达的前驱块选择 x1 或 x2 作为 x3← 正确答案
- D.无条件把 x1 赋给 x3
答案：C。φ 是分拣闸，它的选择依据是控制流从前驱块中的哪一个到达汇合点。不是大小比较，也不是运行时函数调用。
Q6. 关于支配关系，哪些说法正确？
- A.入口支配所有入口可达的基本块← 正确答案
- B.若 d 支配 n 且 d ≠ n，则 d 严格支配 n← 正确答案
- C.每个基本块可以有多个直接支配者
- D.支配关系与 CFG 的边无关
答案：AB。入口到任何可达块的所有路径都必经过入口，所以入口支配所有可达块。严格支配就是支配且不等于自身。直接支配者只有一个，支配关系依赖 CFG 的路径。
Q7. 下面哪些情况会触发布块 b 为变量 x 插入 phi？
- A.b 在 x 某个定义点的支配边界中← 正确答案
- B.x 在 b 的多个前驱块中均有定值且都能到达 b← 正确答案
- C.x 只在 b 内定值并被使用
- D.b 是入口基本块
答案：AB。φ 的本质是多个定义在汇合点合并。定义点的支配边界覆盖了这些汇合位置。如果变量只在块内自产自用，没有多前驱汇合，也不需要 φ。
Q8. 关于支配边界 DF(d)，正确的是？
- A.若 m ∈ DF(d)，则存在 m 的前驱 p 被 d 支配← 正确答案
- B.若 m ∈ DF(d)，则 d 不严格支配 m← 正确答案
- C.若 m ∈ DF(d)，则 m 必被 d 支配
- D.DF(d) 可能为空← 正确答案
答案：ABD。支配边界是“支配力失效”的位置，所以它要求支配某个前驱但不严格支配目标。DF(d) 完全可能为空，比如 d 一直支配到整个图的出口。DF 中的 m 通常不被 d 支配。
Q9. SSA 析构时，为什么不能只删掉 phi？
- A.φ 不是机器可执行指令← 正确答案
- B.φ 表示按前驱选择值，必须转成各前驱里的拷贝← 正确答案
- C.φ 会消耗额外寄存器，删除能提高性能
- D.多个 φ 可能形成并行拷贝，需要临时变量处理覆盖← 正确答案
答案：ABD。φ 是 IR 层的选择指令，CPU 不认识，必须把选择语义下沉到每个前驱块的拷贝里。多个 φ 同时存在时可能互相覆盖，需要临时变量拆成顺序拷贝。
Q10. LLVM 的 mem2reg pass 核心作用是什么？
- A.将
alloca/load/store提升为 SSA 虚拟寄存器← 正确答案 - B.把 SSA 虚拟寄存器降回内存操作
- C.删除所有 phi 函数
- D.将 IR 直接翻译成目标机器码
答案：A。mem2reg 是 LLVM 中最典型的 SSA 构造 pass，它把栈上内存读写提升为虚拟寄存器，并插入必要的 φ，让后续优化在 SSA 上进行。