Sherfiter's wiki for fun

第 9 章 · 数据流分析与优化

前端保证「程序正确」,中端让「程序变快」。本章是编译器的智慧所在:在不改变程序语义的前提下,自动找出可优化的模式。核心方法是数据流分析——在控制流图上迭代求解「每个点程序处于什么状态」的方程,解出来后,优化就有了依据。数据库课第 9 章(查询优化)和本站第 8 章(数据库 WAL)的「分析-决策」结构在此都有远亲。学完这章,你对「编译器背着你做了什么」会有完整的地图。

9.1 控制流图:优化的舞台

把三地址码的指令当节点、跳转当边,得到控制流图(CFG)。基本块(basic block)是 CFG 的节点:一段「只能从第一条进入、只能从最后一条离开」的指令序列,块内顺序执行:

B1:  t1 = 1
     i = 0
B2:  t2 = i < n          ← B1 的后继,循环头
     if !t2 goto B4
B3:  s = s + i           ← 循环体
     i = i + 1
     goto B2
B4:  return s

CFG 上定义两个经典集合:支配关系(dominator,B2 的所有路径必经 B1)、回边(指向支配自己的节点,B3→B2),自然循环 = 回边 + 它圈住的所有节点。循环识别是循环优化的前提,这套图算法(数据结构课第 6 章的图)是中端的地基。

9.2 数据流分析:方程与不动点

数据流分析对每个程序点定义一个「状态」(如「哪些变量此刻是活的」),状态沿 CFG 传播,方程组:

out[B] = merge(in[B1], in[B2], ...)    ← 汇合点怎么合并
in[B]  = transfer(out[B])              ← 块内指令如何改变状态

方向分两种:前向(沿执行方向传播,如到达定值、常量传播)与后向(逆着执行方向,如活跃变量——「之后还会用到吗」天然要从后往前问)。merge 算子也分两种:must(交,所有路径都成立才算成立)与 may(并,任一路径成立即成立)。

解法是迭代到不动点:初值、反复按方程更新、直到不再变化。单调性保证收敛(格理论,离散数学课第 8 章的半序结构在此变现),速度取决于方程的迭代顺序(逆后序遍历能省大量轮次)。

9.3 三个经典分析

活跃变量(live variables)(后向,May):变量 v 在点 p 活跃 = 从 p 出发的某条路径会先读 v 再定义它。用途:寄存器分配(第 10 章,同一时刻活跃的变量不能共用寄存器)、死代码删除(赋值后从不活跃 = 死赋值)。

到达定值(reaching definitions)(前向,May):定值 d(某处对 x 的赋值)能到达点 p = 存在一条路径从 d 到 p 且中途没有重定义 x。用途:常量传播、构建 du 链。

可用表达式(available expressions)(前向,Must):表达式 a+b 在点 p 可用 = 所有到 p 的路径都算过 a+b 且 a、b 未变。用途:公共子表达式删除——x = a+b; y = a+b 的第二个 a+b 可以直接用 x。

每个分析都有「方向 + merge 算子 + transfer 函数」三件套,记住三件套,换任何分析都能推。

9.4 经典优化:分析的受益者

常量传播:到达定值发现 x 的所有定值都是 5,就把用到 x 的地方换成 5,继续折叠 t = 2*3 → t = 6。基于 must 性质(所有路径都常量才算常量)。

死代码删除:活跃变量分析后,「定义后从未活跃」的赋值整条删掉。删掉后可能让别的变量也不活跃,迭代优化(删到不动点)——优化的组合拳是常态。

公共子表达式删除:可用表达式分析后,重复计算直接复用。

循环不变外提:循环里每次都算但结果不变的表达式(a[i]*b 在循环里 i 变了就不行),提到循环前算一次。判据正是数据流:操作数在循环内无定值。

现实的强度顺序:局部优化(块内)> 循环优化 > 全局优化 > 过程间优化(IPA/LTO)。每次 -O2 比 -O0 快几倍,全是这些小优化的复利;对照计组课第 3 章「除法编译成乘法」(强度削减,本家族成员)和第 6 章「分支消除」,你会认出老朋友。

9.5 优化的红线:语义保持

所有优化的大前提:可观察行为不变。什么算可观察?输出、文件、网络;而寄存器怎么用、中间指令怎么排,都不算。这个自由度与语言定义的边界紧密相关——未定义行为给优化器的授权(计组课第 14 章讲过):「有符号溢出不会发生」的假设让优化器敢把 x+1 > x 折叠成 true。C 的优化如此激进,一半功臣(或者祸源)是 UB 授权;Java/Rust 的优化更保守,因为语义定义得更细。

另一个红线:断点可调试性。-O0 忠实逐行,-O2 代码全乱了(变量被优化没了,断点打不上),所以 debug 用 -O0、release 用 -O2,这个习惯的根源就是优化的自由度。

常见错误

  • merge 算子用反。活跃变量(后向 May)在分支汇合用并,常量传播用交(或特殊格);用反则优化错误或永不收敛。
  • 迭代不设限。理论上单调必收敛,实现 bug(transfer 非单调)导致死循环;调试时打印轮次和集合变化。
  • 删了「死代码」却改变行为。那个赋值可能有副作用(函数调用!);死代码删除只对「纯赋值」安全,带调用的要查纯度。
  • 循环不变外提改变异常语义。除零的外提可能让「本来不执行的除法」执行;优化器要确认合法性(而这又常被 UB 授权覆盖,见 9.5)。

练习

  1. 动手:给第 7 章 while 循环的 TAC 画 CFG(标基本块),手工算一遍活跃变量分析(后向迭代两轮),标出每个点的活跃集。
  2. 动手:实现常量传播 mini 版:对线性 TAC,迭代传播「变量 = 常量」信息,把可用处替换、把 if 常量 折叠掉,打印优化前后的指令数。
  3. 手算:x = 1; if (c) x = 2; y = x + 1; 里 y = x + 1 能常量传播吗?用 must 语义推一遍(答案:不能,x 的值路径相关),再想想 SSA 的 φ 函数怎么表达这个「汇合」(第 7 章)。
  4. 思考:编译器凭什么「知道」s = s + i 循环 n 次等价于数学公式?它其实不知道(归纳变量强度削减只是把它变快)。对比「数值程序自动并行化」为什么几十年没做成(依赖分析的完备性、别名问题),体会「优化永远在保守与激进之间走钢丝」。
豫ICP备2026027944号