前置讲 P4 · 编译器入门 · A Gentle Introduction to Compilers

定位：为没有编译器背景的读者补充的前置讲，原课没有对应的课次。它支撑第 9 讲（硬件性能建模：Interstellar 用 Halide 的调度语言描述加速器）、第 12–13 讲（ML 编译器的前端和内核生成）和第 14 讲（智能体生成内核）。建议先读 P1 和 P2。 依据：A. Aho, M. Lam, R. Sethi, J. Ullman, Compilers: Principles, Techniques, and Tools（“龙书”）第 1–2、6、8–9、11 章；R. Cytron et al., Efficiently Computing Static Single Assignment Form（1991）；M. Wolf and M. Lam, A Data Locality Optimizing Algorithm（PLDI 1991）；J. Ragan-Kelley et al., Halide（PLDI 2013）；T. Chen et al., TVM（OSDI 2018）与 L. Zheng et al., Ansor（OSDI 2020）；P. Tillet et al., Triton（MAPL 2019）；C. Lattner et al., LLVM（CGO 2004）与 MLIR（CGO 2021）。 配套代码 Code：code/prereq4/（numpy + 系统的 C 编译器；两个小编译器 mini_compiler.py、loop_ir.py + 5 个脚本，最慢的约 20 秒） 预计阅读时间：3 小时（含运行代码）

0. 本讲导航 · How to read this lecture

0.1 为什么推理课要讲编译器

第 1 讲 §7 的”全栈地图”里，模型和硬件之间隔着两层：内核（一个个在 GPU 上跑的函数）和编译器（把模型变成内核的工具）。原课有 4 次课落在这一层（第 9、12、13、14 讲），这不是偶然：

• 同一个算法，写法不同，速度可以差两个数量级（本讲 §8：512×512 矩阵乘法，最快和最慢的写法差约 195 倍）。手写每一个内核不现实，于是需要编译器替我们写。
• PyTorch 2 的 torch.compile、JAX 的 jit、TVM、Triton、XLA 都是编译器。读懂它们在做什么，才能读懂第 12–13 讲。
• 第 14 讲”让 LLM 写内核”本质上是”用 LLM 代替编译器里的启发式和代价模型”。要评价它，先要知道传统编译器是怎么做的、在哪里会失败。

这一讲不讲编译器的全部（那是一学期的课），只讲后面真正要用的几个概念，而且全部配一个能跑的小编译器：

0.2 学习目标 Learning goals

1. 说出编译器流水线的各个阶段（词法、语法、IR、优化、代码生成）以及为什么要分层；读懂一段 SSA 形式的 IR。
2. 解释常量折叠、代数化简、公共子表达式消除、死代码删除各做什么，以及”优化必须保持语义”在浮点数上意味着什么。
3. 用数据流图分析算子融合省下了多少内存流量、内存规划省下了多少缓冲区；知道融合在什么情况下反而会变慢。
4. 把一个计算写成循环嵌套，求出依赖距离向量，判断循环交换、并行化、循环融合是否合法。
5. 解释循环交换、分块、展开、向量化各自为什么能提速，以及守卫、浮点结合律这些”细节”为什么会让性能断崖。
6. 理解”算法与调度分离”、代价模型和自动调优的分工，以及代价模型为什么总会看错一些东西。

0.3 本讲地图 Map

§1  编译器是什么：一条流水线；为什么分层；ML 编译器有什么不同
§2  前端：词法分析、语法分析、AST                                                ← 代码 01
§3  中间表示：三地址码、SSA、数据流图                                             ← 代码 01
§4  中端：优化 pass——常量折叠、代数化简、CSE、DCE；语义与浮点                      ← 代码 01
§5  后端：指令选择、寄存器分配、向量化；我们怎样"借用"C 编译器                     ← 代码 01
§6  图级优化：数据流图、算子融合、内存规划                                         ← 代码 02
§7  循环嵌套：迭代空间、依赖、合法性                                               ← 代码 03
§8  循环变换：交换、分块、展开与向量化、融合                                        ← 代码 04
§9  算法与调度分离、代价模型与自动调优                                             ← 代码 05
§10 ML 编译器全景：PyTorch 2、JAX / XLA、TVM、Triton、MLIR
§11–15  小结、常见误区、练习（含答案）、延伸阅读、和正课的联系

0.4 关于数字 · About the numbers

• 编译与计数（代码 01、03，以及 02、04、05 里的模拟和计数部分）：每次运行完全相同。
• 墙钟测量（代码 02 演示 4、04、05 的实测部分）：编写时的机器是 Apple M4 Pro（单核）、Apple clang 21、arm64。每次运行会有几个百分点的波动，你的机器和编译器会不同，看形状和倍数。本讲引用的实测数字来自编写时的一次运行。
• 汇编的统计（代码 01 演示 4）取决于你的 C 编译器和 CPU。

1. 编译器是什么 · What a compiler is

1.1 一条流水线

编译器把程序从一种表示翻译成另一种表示，同时尽量让结果跑得快。它不是一步完成的，而是一条流水线，每一步只做一件事：

源代码文本
  │ 词法分析（lexing）        字符 → token（单词）
  │ 语法分析（parsing）       token → 抽象语法树（AST）                    ┐ 前端 front end
  │ 降低（lowering）          AST → 中间表示（IR）                         ┘
  │ 优化（optimization pass） IR → 更好的 IR（很多个 pass，一个接一个）    ← 中端 middle end
  │ 代码生成（codegen）       IR → 目标代码（汇编 / 另一种语言）           ← 后端 back end
  ▼
机器码

1.2 为什么要分层

假设有 $M$ 种源语言、$N$ 种硬件。如果每一对都写一个编译器，要写 $M \times N$ 个；有了一个公共的 IR，只要写 $M$ 个前端和 $N$ 个后端，一共 $M + N$ 个。LLVM 就是这样：C、C++、Rust、Swift、Julia 都编译成 LLVM IR，LLVM 再生成 x86、ARM、RISC-V、NVIDIA PTX 的代码。中端的优化写一次，所有语言、所有硬件都受益。

1.3 ML 编译器有什么不同

ML 编译器（XLA、TorchInductor、TVM、Triton）的骨架一样，但处理的对象不同：

• 输入不是文本，而是一张张量运算的图（矩阵乘法、加法、softmax……），由框架从 Python 程序里”抓”出来（第 12 讲）。
• 最重要的优化不是删掉一两条指令，而是算子融合（少读写几次显存，§6）和循环变换（让数据在 cache / 共享内存 / 寄存器里多用几次，§8）。
• 输出是 GPU / TPU 的内核。硬件太多、形状太多，最优的写法因硬件、因形状而异，所以 ML 编译器特别依赖代价模型和自动调优（§9）。

本讲用两个小编译器把这些都走一遍：mini_compiler.py 处理逐元素的表达式（对应图级编译），loop_ir.py 处理循环嵌套（对应内核生成）。两者都生成 C 代码，交给系统的 C 编译器（clang / gcc）去做最后一步——这也正是真实 ML 编译器的做法：Triton、TVM、XLA 都生成 LLVM IR 或 PTX，再交给 LLVM / NVIDIA 的后端。

2. 前端：词法分析与语法分析 · The front end

代码：01_compiler_pipeline.py

我们的语言只有赋值语句和算术表达式。代码 01 处理的是 LLM 的 FFN 里每层都有的 SwiGLU 激活（故意写得不太好，留给优化器去改）：

c = 0.5 * 2.0;                 # 一个编译时就能算出来的常数
s = 1 / (1 + exp(-g));         # sigmoid(g)
silu = g * s * c;              # 乘以 c（= 1）
gate = g / (1 + exp(-g));      # 和 silu 数学上相同，但写法不同
y = silu * u + 0;              # 加 0
dead = sqrt(abs(u)) * 3;       # 算了但没有人用

2.1 词法分析：字符 → token

词法分析器（lexer）把字符流切成token：数字、名字、运算符。空白和注释在这一步就消失了。代码 01 演示 1：300 个字符变成 63 个 token，第二条语句是

name:s  op:=  num:1  op:/  op:(  num:1  op:+  name:exp  op:(  op:-  name:g  op:)  op:)  op:;

词法分析通常用正则表达式实现（mini_compiler.tokenize 就是一个正则表达式反复匹配）。

2.2 语法分析：token → AST

语法分析器（parser）按文法把 token 组织成树。我们的文法（从低优先级到高优先级）：

expr  := term (('+' | '-') term)*        加减
term  := unary (('*' | '/') unary)*      乘除
unary := '-' unary | atom                一元负号
atom  := NUMBER | NAME | NAME '(' args ')' | '(' expr ')'

递归下降（recursive descent）是最直观的写法：每条规则一个函数，expr 调用 term，term 调用 unary……越”深”的规则绑定得越紧，所以 a + b * c 里的 b * c 先在 term 里组成一个节点。s = 1 / (1 + exp(-g)) 的抽象语法树（AST）：

assign s
  /
    num 1
    +
      num 1
      call exp
        neg
          var g

括号的作用已经体现在树的形状里，括号本身不再需要。AST 仍然很接近源代码，适合检查语法、做简单的解释执行（eval_ast），但不适合优化：优化要把每个运算拆成一步，看清”哪个值被谁用了”。

3. 中间表示：三地址码与 SSA · Intermediate representation

3.1 三地址码

降低（lowering）把 AST 展开成三地址码：每条指令最多一个运算、两个参数、一个结果。代码 01 演示 2 的结果（节选）：

%c1 = mul(0.5, 2)
%t2 = neg(g)
%t3 = exp(%t2)
%t4 = add(1, %t3)
%s1 = div(1, %t4)
...
%t8 = neg(g)            ← 和 %t2 一样
%t9 = exp(%t8)          ← 和 %t3 一样
...
return y = %y1, gate = %gate1

6 条语句展开成 16 条指令。每条指令只做一件事，所以”这个值从哪里来、被谁用到”一目了然——这些”使用”关系连起来，就是数据流图（§6）。

3.2 SSA：每个名字只赋值一次

上面的 IR 遵守静态单赋值（static single assignment，SSA）：每个名字（%s1、%t4……）只被赋值一次。如果源程序给同一个变量赋值两次：

y = a + b;      →    %y1 = add(a, b)
y = y * 2;      →    %y2 = mul(%y1, 2)

IR 会生成两个不同的名字。这样做的好处是：两个名字相同的操作数一定是同一个值，不用担心”中间被改过”。§4 的公共子表达式消除就靠这一点。LLVM IR、MLIR、PyTorch 的 FX graph、XLA 的 HLO、JAX 的 jaxpr 都是 SSA 形式。

（有分支和循环的程序里，同一个变量在不同路径上会得到不同的值，汇合点要用一个特殊的 $\phi$ 函数选择：“如果从左边来，取 $y_1$；从右边来，取 $y_2$“。我们的语言没有分支，用不到它。）

4. 中端：优化 pass · The middle end

一个pass 读入 IR、输出 IR，只做一件事。代码 01 演示 3 依次运行四个 pass，每一步之后都在随机输入上运行 IR、和 AST 解释器的结果比较：

• 常量折叠（constant folding）：参数全是常数的指令，编译时就算出来。c = 0.5 * 2.0 变成常数 1。
• 代数化简（algebraic simplification）：$x \times 1 \to x$，$x + 0 \to x$。
• 公共子表达式消除（CSE）：两条指令的运算和参数完全相同，后一条直接用前一条的结果。实现方法叫值编号（value numbering）：给每个 (运算, 参数) 组合一个编号，查表即可；可交换的运算（加、乘）先把参数排好序。silu 和 gate 都要算 $-g$、$e^{-g}$、$1 + e^{-g}$，只算一次——exp 从 2 次变成 1 次。
• 死代码删除（DCE）：从输出往回找，结果没人用的指令删掉。

16 条指令变成 7 条，结果逐位相同。

两点值得停下来想一想：

1. CSE 只认”写法相同”。它没发现 $g \times (1/t)$ 和 $g / t$ 数学上相等——要发现这种等价，需要更强的技术（例如等式饱和 equality saturation），代价也更大。
2. 优化必须保持语义，而浮点的语义比代数更挑剔。$x \times 0 \to 0$ 在实数里成立，但 $x$ 是 Inf 或 NaN 时，IEEE 754 规定结果是 NaN；$(a + b) + c \to a + (b + c)$ 会改变舍入（P3 §4.2）。真实编译器只在 -ffast-math 这类”允许不严格”的模式下做这些变换（§8.3 会看到它对性能的巨大影响）。

每一步都验证的做法叫差分测试（differential testing）：同一个输入，优化前后（或两个编译器）的结果必须一致。它是编译器测试的主要手段，也是第 14 讲 KernelBench 检查 LLM 生成内核的方法。

5. 后端：从 IR 到机器码 · The back end

5.1 后端要做什么

真实的后端要做三件大事：

• 指令选择（instruction selection）：把 IR 的运算换成目标机器的指令（mul → fmul，乘加合并成 fmadd）。
• 寄存器分配（register allocation）：机器只有几十个寄存器，IR 却有无限多个名字；决定哪些值放寄存器、哪些暂存到内存。
• 指令调度与向量化：重排指令以填满流水线（P1 §1.4），把对 4 个、8 个元素的同一运算合成一条 SIMD 指令。

5.2 我们的后端：生成代码，再借用 C 编译器

mini_compiler 有两个后端（代码 01 演示 4）：

• numpy 后端：每条 IR 指令变成一次 numpy 数组运算。每一行都读完整的输入数组、写一个完整的临时数组——这是不融合的。
• C 后端：一个 for 循环遍历所有元素，循环体里每条 IR 指令变成一个局部变量——这是融合的：每个元素只读一次输入、写一次输出，中间结果都在寄存器里。

void kernel(const float* restrict g, const float* restrict u, float* restrict out_y, float* restrict out_gate, long n) {
    for (long i = 0; i < n; i++) {
        float v_t2 = (-g[i]);
        float v_t3 = expf(v_t2);
        float v_t4 = (1.0f + v_t3);
        ...
        out_y[i] = v_t12;
        out_gate[i] = v_gate1;
    }
}

（restrict 告诉 C 编译器这些指针指向的内存互不重叠——否则编译器担心写 out_y 会改到 g，不敢向量化。）

C 代码交给系统的 C 编译器。代码 01 统计了它生成的汇编：

-O2 把循环向量化了，但 exp 仍然是对 C 库 expf 的标量调用（一个向量里的 4 个数各调一次，再加上处理剩余元素的一次）：通用的 C 库没有向量版本。macOS 上加 -fveclib=Accelerate，编译器会改调向量版的 vexpf。ML 编译器通常自己生成 exp、tanh 的多项式逼近来避免这个问题——§6.4 会看到它对速度的影响有多大。

6. 图级优化：融合与内存规划 · Graph-level optimization

代码：02_dataflow_and_fusion.py

6.1 数据流图

把 IR 里”谁用了谁”连起来，就是数据流图：节点是运算，边是数据。代码 02 用一个 GELU 激活（含偏置和残差）：

h = x + b;
y = 0.5 * h * (1 + tanh(0.7978845608 * (h + 0.044715 * h * h * h)));
out = y + r;

优化后是 11 条指令，排成一条深度为 10 的链。逐元素运算的并行性在”元素”这一维（每个元素独立），而不在图里。%h1 被 5 条指令用到，活得最久；其余临时值大多只用一次，马上就”死”了。

6.2 融合：少读写几次显存

算子融合（operator fusion）把一串运算合成一个内核。逐元素运算每个元素只做几次运算，时间几乎完全由读写的字节数决定（第 1 讲的 roofline：强度远低于屋脊点）。代码 02 演示 2 在 H100 上算账（4096 个 token × $d_\text{ff}$ = 14336，BF16，每个张量 117.44 MB）：

融合把流量降了约 7 倍，时间也降了这么多；内核启动从 11 次降到 1 次（decode 时张量很小，启动开销会成为大头，P2 §8）。但融合后的强度也只有 1.38 FLOP/B，仍然远低于 H100 的屋脊点 295——逐元素运算永远是 memory-bound 的。最好的做法是把它们融合进前后的矩阵乘法里：矩阵乘法写回结果之前顺手做完激活和残差，叫 epilogue fusion，这样它们的读写完全消失（第 10–11 讲）。

6.3 内存规划

不融合时，每个临时值都是一个整张量。朴素地给每个临时值一个缓冲区要 11 个；plan_memory 用贪心算法：一个值最后一次被用到以后，它的缓冲区放回”空闲池”，后面的值复用。结果只需要 3 个（1.29 GB → 352.32 MB）。逐元素运算可以原地计算，链上的大部分值写进同一个缓冲区。PyTorch 的 eager 模式靠缓存分配器在运行时复用显存；XLA、torch.compile 在编译时就做这种规划。融合比规划更彻底：中间结果根本不进显存。

6.4 实测：融合一定更快吗？

代码 02 演示 4 在 CPU 上（1677 万个 float32，单线程）实测同一个 IR 的四种实现（编写时的一次运行）：

写代码之前我预期融合一定更快，结果它慢了 3.8 倍。原因：融合后的循环里，每个元素要调用一次标量的 tanhf（几纳秒），内核从”受限于带宽”变成了”受限于计算”——瓶颈换了地方。numpy 的 tanh 内部是向量化实现，所以不融合反而更快。

把 tanh 换成只用乘、加、除的有理函数逼近（$\tanh x \approx x \cdot P(x^2) / Q(x^2)$，先把 $|x|$ 截到 7.9；系数取自 Eigen 线性代数库），编译器就能把整个循环向量化：7.8 ms，比 numpy 不融合快 3.5 倍以上，误差仍在 float32 舍入的量级（1.4e−6）。

教训：融合解决的是”搬”的问题，但融合后的内核里每个运算都必须高效。这就是为什么 ML 编译器要为 exp、tanh、erf 生成可向量化的多项式逼近，也和第 1 讲 §5.5 的故事一致：FlashAttention-4 用 FMA 单元上的多项式代替一部分 SFU 上的 exp。

7. 循环嵌套与依赖分析 · Loop nests and dependences

代码：03_loop_nests_and_dependences.py

7.1 计算 = 循环嵌套

深度学习的几乎所有算子都是循环嵌套：

for i in range(N):            # C 的行
    for j in range(M):        # C 的列
        for k in range(K):    # 内积
            C[i,j] += A[i,k] * B[k,j]

循环变量 $(i, j, k)$ 的所有取值组成迭代空间（一个 $N \times M \times K$ 的长方体），循环的写法决定了走过这些点的路线。代码 03 演示 1 画出了一个 4×4 空间的三种路线（格子里是执行的先后）：

ij（行优先）       ji（列优先）       2×2 分块
 0  1  2  3        0  4  8 12        0  1  4  5
 4  5  6  7        1  5  9 13        2  3  6  7
 8  9 10 11        2  6 10 14        8  9 12 13
12 13 14 15        3  7 11 15       10 11 14 15

循环变换只改变路线，不改变要走哪些点。如果每个点的计算互不相关，任何路线结果都一样；麻烦在于点之间常常有依赖。

7.2 依赖与距离向量

两次访问读写同一个内存位置、而且至少有一次是写，它们之间就有依赖：先执行的那个必须仍然先执行。三种依赖：

• RAW（read after write，真依赖 flow）：后者要用前者算出的值；
• WAR（write after read，反依赖 anti）：后者不能提前覆盖前者要读的值；
• WAW（write after write，输出依赖 output）：最后留下的必须是后写的那个值。

距离向量 = 终点的迭代向量 − 起点的迭代向量。代码 03 演示 2 枚举了五个经典例子（loop_ir.dependences 在小规模上把所有迭代走一遍，找出读写同一元素的迭代对）：

真实编译器不能”枚举”（$N$ 可能是几千），它们把”是否存在两个迭代访问同一个元素”写成整数线性方程组来解——这是多面体模型（polyhedral model）的核心，第 13 讲会提到。小规模枚举得到的距离和解析解一样（下标都是仿射的），更容易看懂。

7.3 合法性：三条规则

规则 1（循环交换）：一个新的循环顺序合法，当且仅当每个依赖的距离向量按新顺序排列后字典序仍然为正（第一个非零分量 > 0）。

规则 2（并行）：一层循环可以并行执行，当且仅当没有依赖由它”携带”（按当前顺序，没有哪个距离向量的第一个非零分量落在这一层）。

规则 3（融合）：两个循环可以融合，当且仅当所有”从第一个循环到第二个循环”的依赖距离 ≥ 0。

代码 03 演示 3 对每个例子、每种顺序既用规则判断，又真的执行一遍和原顺序比较：

• 矩阵乘法 6 种顺序全部合法，结果逐位相同；$i$、$j$ 两层可以并行——GPU 给每个输出（块）一个线程（块），正是在并行 $i$、$j$。$k$ 方向的累加在一个线程里顺序做，或者用 split-K 拆开再归约（P2 §7）。
• 斜向依赖 (1, −1) 交换成 $ji$ 后变成 (−1, 1)：终点跑到了源头前面。依赖分析判为不合法，实际执行的结果真的不同了。
• 二维递推两层都携带依赖，都不能直接并行；但同一条反对角线（$i + j$ 相同）上的点互不依赖——倾斜（skewing）变换能把它们变成一层可以并行的循环（波前并行）。
• Jacobi 没有跨迭代依赖，所有点都能同时算。这就是为什么 GPU 上的计算几乎都写成”读输入、写另一个输出”的形式。

演示 4 检验融合：生产者 B[i] = A[i] * 2 和消费者 C[i] = B[i] + 1 的依赖距离是 0，融合合法，而且 B 刚算出来就被用掉，可以留在寄存器里；消费者改成读 B[i+1] 时距离是 −1，融合后读到的是还没生产的值，结果真的错了。修复办法是把消费者”平移”一步（第 $i$ 次迭代算 $C[i-1]$）。神经网络的逐元素算子几乎都”读同一个位置”，所以总能融合；读”邻居”的算子（卷积、注意力）融合起来就要精心设计——FlashAttention 就是一次精心设计的融合（第 11 讲）。

8. 循环变换 · Loop transformations

代码：04_loop_transformations.py

§7 回答了”哪些变换合法”，这一节回答”哪些变换有利、利有多大”。主角是矩阵乘法：同一个算法、同样的运算次数，只是换个写法。

8.1 循环交换：最内层决定一切

代码 04 演示 1 对 6 种循环顺序：先用 P1 的 cache 模拟器（4 KiB、4 路组相联、3C 分类）在 64×64 的矩阵上数缺失，再生成 C 代码、在 512×512 上实测（-O2，编写时的一次运行）：

• ikj、kij 的最内层是 $j$：B 和 C 都按行连续访问，A 不动，缺失率最低；连续访问还能向量化。
• jki、kji 的最内层是 $i$：A 和 C 每一步跳过一整行，每次访问都碰一个新的 cache line；一列 64 行、两列 128 行，超过 4 KiB cache 的 64 行——缺失几乎全是容量缺失（我原以为是 P1 讲过的冲突缺失，模拟器显示 4 路组相联已经化解了大部分冲突）。
• ijk、jik 的最内层是 $k$：A 连续、B 跳行，而且所有 $k$ 都加到同一个 C[i,j] 上——一条依赖链（P1 §1.6），每次加法都要等上一次完成，也不能向量化。

最快和最慢差约 56 倍。实测的差距比缺失数的差距更大，因为向量化和依赖链这两个因素模拟器看不见。

8.2 分块：让数据在 cache 里多用几次

分块（tiling）= 把每个循环拆分（strip-mining：$i \to (i_o, i_i)$，$i = 32 i_o + i_i$），再把外层的块循环提到前面：

for io, ko, jo:                          # 遍历块
    for ii, ki, ji:                      # 块内（ikj 顺序）
        C[io*T+ii, jo*T+ji] += A[io*T+ii, ko*T+ki] * B[ko*T+ki, jo*T+ji]

块内的 A、B、C 子矩阵一共 $3T^2$ 个数。它们放得进 cache 时，块内的计算全部命中，每个数被复用 $T$ 次。（分块合法吗？它是”拆分”加”交换”，矩阵乘法的任何交换都合法，所以合法。一般地，要求块内的几层循环”完全可交换”。）

代码 04 演示 2（模拟 64³、4 KiB 全相联；实测 512³）：

三个现象：

1. 模拟里，工作集放得进 4 KiB 时（T ≤ 16）缺失数降到不分块的 14%；放不下以后回到原来的量级。块大小要和 cache 大小匹配。
2. 实测里，最快的是 T = 8（约 3.2 倍于不分块）。真实 CPU 的 L1 有 128 KiB、L2 有 16 MiB，512×512 的矩阵本来就放得进 L2，所以 L1 的分块收益没有模拟里那么夸张；T = 8 快，主要是因为块内循环短到能被编译器完全展开、数据留在寄存器里——这叫寄存器分块，是第 10 讲 GPU 矩阵乘法内核的核心。
3. 不整除的块慢了约 25 倍。512 不能被 24、48 整除，split 自动加了一个守卫 if (i < 512) 保证不越界，结果正确，但最内层的 if 让编译器无法向量化。写代码之前我以为守卫”只是多一个比较”。实际的编译器会把”整块”和”剩下的边角”分开生成两份代码，热循环里不做判断。

8.3 编译选项与浮点结合律

代码 04 演示 3：

• -O0 到 -O2 快了约 94 倍：寄存器分配、循环不变量外提、展开、向量化都是后端在做。我们的循环 IR 只负责”循环怎么排”。
• 点积形式：先把 B 转置成 BT，C[i,j] += A[i,k] * BT[j,k]，最内层两个输入都连续访问，看起来很理想，-O2 下却很慢。最内层是对同一个 C[i,j] 的累加：编译器必须保持”从 $k = 0$ 加到 $k = N - 1$“的顺序，只能一个一个加。
• 加 -ffast-math 快了约 7 倍：编译器被允许重新结合加法——开几个部分和并行累加、最后合并，这就是向量化的归约。代价是结果不再和”逐个累加”逐位相同。有意思的是，最大误差反而从 1.1e−4 降到 1.3e−5：几个部分和分开累加，相当于部分的”两两求和”（P3 §4.4）。

能不能重排求和顺序，是语义问题，不是性能问题。GPU 上的归约、Tensor Core 内部的累加顺序、多卡 all-reduce 的顺序，都在做同样的取舍。

8.4 循环融合

代码 04 演示 4：生产者 B[i,j] = A[i,j] * 2、消费者 C[i,j] = B[i,j] + A[i,j]。不融合时读 A、写 B，再读 B、读 A、写 C，一共 5 遍；融合后，消费者要的 B 和 A 刚被碰过、还在 cache 里，只剩 3 遍。模拟的缺失数正好降了约 1.67 倍（5,120 → 3,072）；2048×2048 上实测从 0.6 ms 降到 0.4 ms。如果 B 只是中间结果，融合后甚至可以不写 B，只剩 2 遍。

融合和分块是同一个思想的两面：让数据在离计算单元最近的存储里被尽量多地使用，再被扔掉。

8.5 其他变换（简述）

• 展开（unrolling）：把循环体复制几份、减少循环控制的开销，并给指令调度更多选择。我们的 unroll 只是一个提示（#pragma），要不要展开最后由 C 编译器决定。
• 向量化（vectorization）：把最内层的连续几次迭代合成一条 SIMD 指令。前提：连续访问、没有（或者允许重排的）依赖、没有分支。
• 倾斜（skewing）：改变迭代空间的坐标，让有依赖的循环出现可以并行的一层（§7.3）。
• 软件流水（software pipelining）、双缓冲：让下一块数据的读取和这一块的计算重叠（第 10 讲）。

9. 算法与调度分离、代价模型与自动调优 · Schedules, cost models, autotuning

代码：05_schedules_and_autotuning.py

9.1 算法与调度分离

§8 的每一个写法都在改循环，但语句本身一字未改。Halide（2013，图像处理）把这个观察做成了语言：

• 算法（algorithm）：算什么。C[i,j] += A[i,k] * B[k,j]。
• 调度（schedule）：怎么算。split(i, 32); split(j, 32); split(k, 32); reorder(io, ko, jo, ii, ki, ji); unroll(ki, 4)。

loop_ir 就是这样设计的：语句永远用原始变量书写，调度原语只改变循环结构和”原始变量怎样由循环变量算出来”（$i = 32 i_o + i_i$）。正确性由算法保证（只要调度合法），性能由调度决定，于是可以放心地试很多调度。TVM 把它搬到了深度学习；Triton 走得更远，让程序员直接写”块级”的程序，块内的线程映射、向量化、共享内存交给编译器（第 13 讲）。第 9 讲的 Interstellar 则用 Halide 的调度语言来描述硬件加速器的数据流——“调度”这个概念从软件延伸到了硬件。

9.2 代价模型：不运行，靠分析预测

调度空间很大：循环顺序 × 每一层的块大小 × 展开 × 向量化 × 并行……真实的空间动辄上万个点。一个个编译运行太慢，于是需要代价模型（cost model）：不运行，靠分析预测哪个快。

loop_ir.predict_misses 是一个最简单的解析模型：从最内层往外找，找到”执行一遍时工作集还放得进 cache”的最外层 $L$，认为第 $L$ 层每执行一次就要把工作集整个搬一遍：

代码 05 演示 2 在小规模（48³、4 KiB cache）上把它和 LRU 模拟比较：绝对数值偏差很大（预测 / 模拟在 1.3–16.6 倍之间，因为它忽略了相邻两次执行之间的数据重叠，总是高估），但排序相当一致（Spearman 等级相关 0.87）。对编译器来说，代价模型只要排序对，不必数值准。

9.3 在真实机器上检验代价模型

代码 05 演示 3 在 512³ 上编译运行了 36 个调度（6 种不分块的顺序 + 5 种块大小 × 2 种块顺序 × 3 种块内顺序），并用三个越来越”聪明”的代价模型预测：

• v1：只看 cache（上面的 predict_misses）；
• v2：v1 + 计算时间——最内层如果是归约（依赖链）就慢，连续访问（可向量化）就快，否则居中；
• v3：v2 + 一条规则：“范围 ≤ 16 的最内层归约会被编译器完全展开，转而向量化外面一层”。

编写时的一次运行：

（名字里竖线左边是块的遍历顺序，右边是块内的循环顺序。）预测和实测的 Spearman 相关：v1 = 0.26，v2 = 0.53，v3 = 0.64（各次运行略有不同）。

这张表讲了一个关于代价模型的完整故事：

1. v1 只看见 cache，分得清”分块 vs 不分块""最内层连续 vs 跳跃”，却看不出同样分块时块内最内层是归约还是可向量化——长归约的调度缺失很少，实测却慢 20 多倍。
2. v2 加了”最内层特征”，相关提高了；但它把实测最快的调度（T8、块内最内层是 8 次的 k 归约）判成了”慢”：编译器把这么短的循环完全展开，转而向量化外面的 j 循环。代价模型必须同时模拟”下游编译器会做什么”。
3. v3 补上了这条规则，相关又提高了。但请注意：这条规则是我看了实测结果之后才加的。代价模型在实践中就是这样被一条条”调”出来的，也因此容易只适用于某个编译器、某台机器。TVM 的 Ansor 等系统干脆用实测数据训练代价模型（学习型代价模型）。
4. 三个模型的首选都是”缺失最少的大块”（T64），实测却比最快的慢约 2.3 倍：T = 8 的小块快在寄存器级的复用，而我们的模型只看到了 L1。模型总是只看见它被设计去看的那一层。

9.4 自动调优：搜索策略

自动调优（autotuning）= 真的编译、运行、计时，挑最快的。代码 05 演示 4 在演示 3 测好的表上回放三种策略（预算 $b$ = 实测的次数；指标 = 找到的最快时间 / 真正最快的时间）：

写代码之前我预期”模型引导总比随机好”，结果预算很小时，模型引导反而不如随机搜索：模型最看好的几个调度都是它系统性看错的那一类，一个有偏的模型会把搜索稳稳地带到错的地方。模型的价值是把明显很差的调度（不分块、跳跃访问、长归约）排除掉，而不是直接选出最优。所以实际系统总是”模型筛选 + 实测”：

• AutoTVM / Ansor：学习型代价模型 + 进化搜索，模型挑出有希望的候选，再实测、再用实测数据更新模型；
• Triton 的 @autotune：程序员列出几个配置，全部实测，按输入形状缓存最快的；
• cuBLAS / CUTLASS：为常见形状预先调好，运行时用启发式选；
• 第 14 讲的 LLM 写内核：用 LLM 代替代价模型提出候选，再用实测（AlphaEvolve 的”评估器”）来评判。

10. ML 编译器全景 · The ML compiler landscape

把本讲的概念放到真实系统里（第 12–13 讲会展开）：

每一行都是本讲的流水线：前端得到 SSA 形式的图（§3），图级 pass 做融合和内存规划（§6），循环级 IR 上做变换和调度（§7–9），最后交给 LLVM 之类的后端（§5）。

11. 小结 · Summary

1. 编译器是一条流水线：词法 → 语法 → IR → 优化 pass → 代码生成。公共的 IR 让 $M$ 种语言和 $N$ 种硬件只需 $M + N$ 个组件。
2. SSA 形式的 IR 让”一个值从哪来、被谁用”一目了然，常量折叠、化简、CSE、DCE 都很简单；但优化必须保持语义，浮点的语义比代数更挑剔。
3. 融合省掉中间结果的读写，逐元素运算的时间几乎正比于字节数，所以收益很稳——但融合后的内核里每个运算都要高效，标量的 tanhf 就能让它慢 4 倍。内存规划让临时缓冲区可以复用。
4. 依赖分析用距离向量判断变换是否合法：交换后字典序仍为正、并行的那层不携带依赖、融合后距离 ≥ 0。
5. 循环变换：最内层循环决定局部性和能否向量化；分块让工作集放进 cache / 寄存器；守卫和浮点归约会让性能断崖；-O 级别和 -ffast-math 是后端的事，但影响巨大。
6. 算法与调度分离让我们放心地搜索调度；代价模型只需排序对，但总会系统性地看错它看不见的层次；所以实际系统是”模型筛选 + 实测”。

12. 常见误区 · Common pitfalls

1. “编译器会自动把我的循环优化到最好。” 通用编译器（clang / gcc -O2）一般不做循环交换和分块（§8.1 里最快和最慢的循环顺序差约 56 倍，-O2 一点没帮上）；它擅长的是指令级的优化。循环级的决策正是 ML 编译器和调度语言要做的。
2. “融合一定更快。” 融合省的是内存流量；如果融合后的内核受限于计算（标量的超越函数、寄存器不够），可能反而更慢（§6.4）。
3. “CSE 能发现所有重复计算。” 它只认写法相同的表达式（§4）。
4. “把 x * 0 化简成 0 总是对的。” Inf × 0 = NaN；类似地，重排浮点加法会改变结果（§4、§8.3）。
5. “分块大小随便选一个 2 的幂就行。” 太大放不进 cache，太小复用不够；不整除时的守卫可能让性能慢一个数量级（§8.2）。
6. “代价模型预测的时间可以直接用。” 解析模型的数值常常差好几倍，有用的只是排序，而且排序也会系统性地出错（§9.2–9.3）。
7. “有了代价模型就不需要实测。” 预算很小时，有偏的模型可能不如随机搜索（§9.4）。

13. 练习 · Exercises

带 💻 的题可以用本讲的代码验证。参考答案在每题后面。

练习 1（语法树）。画出 a - b - c 和 a - (b - c) 的 AST。我们的文法（expr := term (('+' | '-') term)*）把 a - b - c 解析成哪一种？为什么减法必须这样？

文法里 while 循环每次把已有的 node 作为左孩子：a - b - c 解析成 (a - b) - c（左结合）。减法不满足结合律，$a - (b - c) = a - b + c$，所以必须左结合，否则 $10 - 3 - 2$ 会算成 9 而不是 5。验证：ast_to_str(parse("y = a - b - c;")[0]) 的根节点是 -，左孩子又是一个 -。

练习 2（SSA）💻。把下面的程序降低成 SSA IR：y = x + 1; y = y * y; z = y + x;。一共几条指令？y 变成了几个名字？

%y1 = add(x, 1)，%y2 = mul(%y1, %y1)，%z1 = add(%y2, x)，3 条指令；y 变成 %y1 和 %y2 两个名字。用 print(ir_to_str(*lower(parse(src), ["z"])[:2])) 验证。

练习 3（优化 pass 的顺序）💻。程序 a = x * (3 - 3); b = a + y;。按”常量折叠 → 代数化简 → CSE → DCE”的顺序，每一步之后剩什么？如果先做代数化简再做常量折叠，结果一样吗？

降低后：%t1 = sub(3, 3)、%a1 = mul(x, %t1)、%b1 = add(%a1, y)。常量折叠：%t1 → 0，得 %a1 = mul(x, 0)。代数化简：mul(x, 0) → 0，于是 %b1 = add(0, y) → y，最后输出直接就是 y，没有指令。先化简后折叠：化简时 %t1 还不是常数，mul(x, %t1) 化简不了；折叠后虽然变成 mul(x, 0)，但化简已经做过了——剩下 2 条指令。pass 的顺序会影响结果，所以真实编译器会把一组 pass 反复运行直到不再变化（不动点）。（再次提醒：x * 0 → 0 在浮点里不安全。）

练习 4（融合的流量账）。一个逐元素的 LayerNorm 后处理：y = (x - mu) * rstd * w + b（x、w、b 是张量，mu、rstd 每行一个数，忽略它们的流量）。不融合（每个二元运算一个内核）和融合时，各读写几个整张量？

4 个运算：t1 = x - mu（读 x、写 t1 = 2）、t2 = t1 * rstd（2）、t3 = t2 * w（读 t2、w，写 t3 = 3）、y = t3 + b（3），一共 10 个；融合：读 x、w、b，写 y = 4 个。流量少 2.5 倍。

练习 5（依赖距离）💻。求 A[i+1,j+2] = A[i,j] + 1 的依赖距离。交换 $i$、$j$ 合法吗？哪层可以并行？

第 $(i, j)$ 次迭代写 $A[i+1, j+2]$，第 $(i+1, j+2)$ 次迭代读它：RAW，距离 (1, 2)。交换后 (2, 1)，字典序仍为正，合法。原顺序下依赖由 $i$ 层携带，$j$ 层可以并行；交换后由 $j$ 层携带，$i$ 层可以并行。用 dependences(LoopNest([("i", 5), ("j", 5)], ["A[i+1,j+2] = A[i,j] + 1"], {"A": (7, 8)})) 验证。

练习 6（融合的合法性）。生产者 B[i] = A[i] + 1，消费者 C[i] = B[i-1] * 2（$i \ge 1$）。依赖距离是多少？融合合法吗？

B[i−1] 在第 i−1 次迭代写、第 i 次迭代读：距离 +1 ≥ 0，合法。融合后第 i 次迭代读的 B[i−1] 已经在上一次迭代写好了（不过不能再”留在寄存器里”直接用，要跨一次迭代保存）。

练习 7（分块的工作集）。一个 L1 有 48 KiB 的 CPU，float32 矩阵乘法、方块 $T \times T$。块内三个子矩阵都要放进 L1，$T$ 最大取多少（取 2 的幂）？如果是 BF16 呢？

$3 T^2 \times 4 \le 49{,}152$ → $T \le 64$；BF16（2 字节）：$3 T^2 \times 2 \le 49{,}152$ → $T \le 90$，取 2 的幂是 64，或者取 80 这样的非 2 的幂（注意整除和守卫的问题，§8.2）。实际中还要给预取、栈等留余量，常取再小一些。

练习 8（向量化与结合律）。为什么 for k: s += a[k] * b[k] 在 -O2 下不能向量化，而 for j: c[j] += a * b[j] 可以？

前者所有迭代都加到同一个 s 上，向量化需要开多个部分和、最后合并，改变了加法顺序，浮点结果会变，编译器默认不做（要 -ffast-math 或 #pragma clang loop vectorize(assume_safety) 之类的许可）。后者每个 $j$ 写不同的 c[j]，迭代之间没有依赖，向量化不改变任何一次运算的顺序。

练习 9（代价模型）💻。用 predict_misses 预测 64³ 矩阵乘法 ijk 和 ikj 在 4 KiB cache、64 字节一行时的缺失数，再用 lru_misses 模拟。预测的比值和模拟的比值各是多少？

预测：ijk 1,048,576（连最内层的工作集都放不下，按每次访问都缺失估计）、ikj 36,864，比值约 28。模拟（lru_misses(nest.address_trace(default_layout(nest.shapes)), 4096, 64)）：ijk 262,656、ikj 16,896，比值约 16。模型对 ijk 高估了 4 倍——它没有考虑相邻的 k 迭代共享 A 的同一个 cache line；对 ikj 高估约 2 倍。两个比值都说明”ikj 好得多”，这正是 §9.2 说的”数值不准，排序大致对”。

练习 10（搜索预算）。一个调度空间有 1000 个点，其中最快的 1% 都”足够好”。随机搜索要实测多少次，才有 95% 的把握至少碰到一个”足够好”的？

每次碰到的概率 0.01，$b$ 次都碰不到的概率 $0.99^b \le 0.05$ → $b \ge \ln 0.05 / \ln 0.99 \approx 298$。随机搜索的代价随”好点的比例”而不是空间大小变化——这就是为什么好的代价模型（把好点的比例提高）这么有价值，哪怕它不完美。

14. 延伸阅读 · Further reading

• A. Aho et al., Compilers: Principles, Techniques, and Tools（龙书）：第 2 章（一个完整的小编译器）、第 8 章（代码生成）、第 9 章（数据流分析）、第 11 章（并行性与局部性优化：依赖、仿射变换、分块）。
• K. Cooper and L. Torczon, Engineering a Compiler：比龙书更现代、更好读。
• M. Wolf and M. Lam, A Data Locality Optimizing Algorithm（PLDI 1991）：循环交换、分块与复用分析的经典论文。
• J. Ragan-Kelley et al., Halide: A Language and Compiler for Optimizing Parallelism, Locality, and Recomputation in Image Processing Pipelines（PLDI 2013）：算法与调度分离。
• T. Chen et al., TVM（OSDI 2018）；L. Zheng et al., Ansor（OSDI 2020）：深度学习的调度搜索与学习型代价模型。
• P. Tillet et al., Triton: An Intermediate Language and Compiler for Tiled Neural Network Computations（MAPL 2019）。
• J. Ansel et al., PyTorch 2: Faster Machine Learning Through Dynamic Python Bytecode Transformation and Graph Compilation（ASPLOS 2024）：TorchDynamo 与 TorchInductor。
• C. Lattner et al., MLIR: Scaling Compiler Infrastructure for Domain Specific Computation（CGO 2021）。

15. 和正课的联系 · Where this shows up

• 第 9 讲（硬件性能建模）：DNN 计算 = 循环嵌套（§7）；“数据流”（weight / output / row stationary）= 循环顺序 + 并行展开；分块 = 映射到存储层次（§8.2）；Interstellar 用 Halide 的调度语言描述加速器（§9.1），能量模型就是 §9.2 那种”每层访问次数 × 每次的代价”。
• 第 10 讲（内核开发）：分块矩阵乘法内核的每一步（合并访存 → 共享内存分块 → 寄存器分块 → 双缓冲）都是本讲的循环变换在 GPU 上的版本。
• 第 11 讲（内核优化）：FlashAttention 是一次精心设计的融合（§7.3、§6）；megakernel 是把融合做到极致——整个模型一个内核。
• 第 12 讲（ML 编译器前端）：图捕获（TorchDynamo、jaxpr）、SSA 形式的图 IR、图级 pass（§3–§6）。
• 第 13 讲（内核生成）：调度语言、Triton、多面体模型、自动调优与代价模型（§7–§9）。
• 第 14 讲（智能体生成内核）：KernelBench 的正确性检查就是差分测试（§4）；AlphaEvolve 的”LLM 提出 + 评估器打分”就是”代价模型提出 + 实测”（§9.4）的新版本。