结果相同、代价更低的程序 — CFG 与 SSA

一句话总结

优化就是把程序换成结果相同、但开销更低的程序。在树上，做法是提前计算常量、清除已经确定的分支；在指令列表上，则是建立基本块和控制流图（CFG），删除没有路径可达的代码。在这张图上求出支配节点之后，就能进一步算出实用编译器的中间表示 SSA 把 φ 放在哪里。

为什么需要它

人写代码是为了好读。会写 60 * 60 * 24 而不是 86400，会留下调试用的 if (false) { … }，有时还会在 return 后面留几行。第 6 个模块的编译器会把这些原样翻译，所以循环里的 60 * 60 * 24，每转一圈就是两次乘法。如果编译器能替人提前算好，人就既能写出好读的代码，又能得到快的程序。

不过，优化有一条不能越过的线。结果不能改变。不能因为想把 7 / (3 - 3) 当作“是常量，所以提前计算”，就让编译器崩溃，或者把错误消除掉——这一行在运行时必须就地报出除以 0 的错误。好的优化器，先知道的是不能做什么，其次才是能做什么。

工作原理

常量折叠。从下往上遍历树，把两边都是字面量的运算算出来，换成一个字面量。64 位回绕和向 0 截断的除法，要与解释器完全一致；而执行时会出错的表达式（除以 0、负指数、类型不匹配的运算），则不折叠，保留原样。折叠出的字面量继承原运算符的位置。false && f() 的右边不会被执行，所以整个就是 false，而 true && e 就是 e。if (true) 变成它的那个分支（保持块的原样——为了让作用域保留），while (false) 则整个消失。

基本块与 CFG。在指令列表里，把第一条指令、跳转的目的地，以及跳转和 RETURN 的正后方标为“首指令（leader）”，从一个首指令到下一个首指令之前，就是一个基本块。进入块内部只能经过第一条指令，离开只能经过最后一条指令。给每个块记下它的后继块（顺序落入的一边、跳转的一边），就是 CFG。从入口出发沿着 CFG 走不到的块，可以删掉——本课程的编译器会在每个函数末尾附上 CONST 0 · RETURN，所以每个以 return 结尾的函数里，这两条指令都会作为不可达代码留下来。删掉之后，剩下的跳转的偏移量必须按新的位置重新计算。

fn pos(v) { if (v < 0) { return 0; } return v; }

 B0  0 GET_LOCAL 0         B0 → B1(흘러내림), B2(점프)
     1 CONST 0   ; 0
     2 LT
     3 JUMP_IF_FALSE 2 ; → 6
 B1  4 CONST 0   ; 0       B1 → 없음(RETURN)
     5 RETURN
 B2  6 GET_LOCAL 0         B2 → 없음
     7 RETURN
 B3  8 CONST 0   ; 0       ← 입구에서 닿지 않는다(컴파일러가 붙인 꼬리): 지운다
     9 RETURN

支配节点与 SSA。块 d 支配块 b，意思是从入口到 b 的所有路径都经过 d。所有块的支配节点集合，通过反复应用“b 的支配节点 = {b} ∪（前驱块们的支配节点的交集）”，直到不再变化为止来求出。为什么需要它——实用编译器（LLVM、GCC）的中间表示是 SSA，也就是每个变量只被赋值一次的形式。把 x = 1; if (c) x = 2; print x; 变成 SSA，会得到 x1 = 1、x2 = 2，以及在两条路径汇合的地方的 x3 = φ(x1, x2)。φ 的意思是“根据是从哪条路来的来选择”。

      B0: x1 = 1; if c
       /          \
  B1: x2 = 2       |
       \          /
      B2: x3 = φ(x1, x2); print x3        ← B2 는 B1 의 지배 경계

φ 放在哪里，由支配边界（dominance frontier）告诉我们。块 b 的支配边界，是从 b 所支配的区域向外走一步，第一次支配中断的那些块——也就是从 b 来的值与从别的路来的值第一次相遇的地方。在变量被赋值的那些块的支配边界上放置 φ，并且把新放置的 φ 也当作赋值，一直扩展到不再增加为止（迭代支配边界）。

在现场相遇的样子

• -O2 的几乎所有工作都在这张图上进行。常量传播、死代码消除、公共子表达式消除、把计算提到循环外面，全都是在 SSA 和 CFG 上做的计算。因为在 SSA 里每个变量只有一个定义，“这个值从哪里来”一眼就能看到。到第 10 个模块打开 clang 的 LLVM IR 时，你会亲眼看到 phi 指令。
• 优化暴露出 bug 的时候。“-O0 下正常，-O2 下结果不同”，多半不是优化器的 bug，而是程序存在未定义行为（比如有符号整数溢出），优化器把它当成“不会发生的事”而删掉了。不改变结果的承诺，只对有定义的行为才会遵守。
• 调试变难的原因。优化后的代码里，变量显示为 “optimized out”，是因为该变量被拆成了 SSA 中的多个值，其中一部分消失了。

下一项实验要做什么

在 opt.py 中做出表达式折叠、程序折叠（清除已确定的分支）、基本块、CFG、删除不可达块（重新计算跳转）、支配节点与直接支配节点、支配边界与 φ 的位置，以及折叠 → 编译 → 删除的流水线。评分器会把树、chunk 和图与参考对照，并用 VM 确认优化后的程序在得出同样结果的同时，执行了更少的指令。