机器无关优化
机器无关优化
机器无关优化(Machine-Independent Optimization)是编译器中端的核心工作,它以中间表示(IR)为输入,对代码进行变换以提升执行效率,同时不依赖任何具体的目标机器。因为它只操作 IR,所以一份优化实现能被 x86、ARM、RISC-V 等多个后端复用,是现代编译器"前端 → IR → 优化 → 后端"架构的关键一环。
通俗理解:就像装修图纸阶段的优化——房子还没盖,但你可以先在图纸上把不必要的房间去掉、把重复的走线合并。这些改动跟砖头是红是灰、地板是木是瓷无关;等到具体施工(代码生成)时,再针对材料差异做调整。
机器无关优化的两条主线是局部优化(基本块内部)和全局优化(跨基本块,基于控制流图)。全局优化又依赖数据流分析来收集"程序某一点上的信息"。
局部优化
基本块是一段线性执行的代码,中间没有跳入跳出,是最容易分析的单位。常见的局部优化包括:
- 常量折叠:编译期计算常量表达式,
3 + 4直接变成7。 - 常量传播:变量已知为常量时,把用到它的地方也替换成常量。
- 公共子表达式消除(CSE):同一表达式计算过就复用结果。
- 代数化简:
x * 1 → x、x + 0 → x、x * 0 → 0。 - 复制传播:
y = x; z = y + 1变成z = x + 1。 - 死代码消除(DCE):结果没被用到的赋值直接删掉 。
一段前后对比:
// 优化前
a = 2 + 3;
b = a * 1;
c = a + b;
d = c;
e = c + 0;
f = a * 3; // f 之后没被使用
// 常量折叠、代数化简、复制传播、死代码消除后
a = 5;
b = 5;
c = 10;
d = 10;
e = 10;
配合 CSE 与进一步的常量传播,上面这段几乎所有计算都能在编译期完成。
循环优化
程序 90% 以上的时间花在循环里,所以循环优化收益最大。
循环不变量外提(LICM):如果表达式在循环内每次求值都得到相同结果,就把它提到循环之外。
for (int i = 0; i < n; i++) {
a[i] = x * y + i; // x * y 是循环不变量
}
// 外提后
int t = x * y;
for (int i = 0; i < n; i++) {
a[i] = t + i;
}
归纳变量识别与强度削减:循环里形如 j = i * 4 的量叫归纳变量。可以把每次的乘法换成加法:
for (int i = 0; i < n; i++) {
a[i * 4] = 0; // 每次做一次乘法
}
// 强度削减
for (int p = 0; p < n * 4; p += 4) {
a[p] = 0; // 变成加法
}
循环展开:将循环体复制多份,减少分支判断次数,也给流水线更多调度机会。循环合并把两个遍历同一范围的循环合成一个,减少循环开销和缓存缺失;循环分裂则反过来,把一个大循环拆成两段,让每部分能独立优化。
数据流分析框架
跨基本块的信息必须靠数据流分析(Dataflow Analysis)来传递。整个框架由四个组件构成:
- 格(Lattice):每个程序点上的信息取值组成一个偏序集合,通常带有 top 和 bottom。
- 传递函数:描述一条语句如何把入口信息变成出口信息。
- 汇合运算:控制流合流时,如何把多条路径的信息合并(∪ 或 ∩)。
- 迭代求解不动点:反复应用传递函数直到信息不再变化。
只要问题能被形式化成这四件套,就能套用同一个通用求解器。这正是数据流分析强大的原因。
四类经典数据流问题
按"方向 × 汇合运算"分类,最经典的有四种:
| 问题 | 方向 | 汇合 |
|---|---|---|
| 到达定值(Reaching Definitions) | 正向 | ∪ |
| 活跃变量(Liveness) | 反向 | ∪ |
| 可用表达式(Available Expressions) | 正向 | ∩ |
| 极忙表达式(Very Busy Expressions) | 反向 | ∩ |
"正向"指信息从入口流向出口,"反向"指从出口流向入口。举个直观例子:
1: x = 1;
2: y = x + 2;
3: print(y);
- 到达定值(正向):在语句 2 前,"x=1" 这个定值已经到达了这里。
- 活跃变量(反向):在语句 1 之后,x 是活跃的(后面还会被读);到语句 2 之后 x 就不再活跃。
方向决定了迭代时是"顺着流图走"还是"逆着走",汇合决定了"任一路径成立就算成立(∪)"还是"所有路径都成立才算成立(∩)"。
SSA 形式
SSA(Static Single Assignment,静态单赋值)要求每个变量在程序中只被赋值一次。多路径合流时,用 Φ 函数选择来自哪条路径的值:
// 原始代码
if (cond) x = 1;
else x = 2;
y = x + 1;
// SSA 形式
if (cond) x1 = 1;
else x2 = 2;
x3 = φ(x1, x2);
y1 = x3 + 1;
Φ 函数应放在支配边界上——即刚好脱离某个基本块支配范围的那些位置。SSA 让"某变量的定义在哪里"变得唯一,很多优化(常量传播、DCE、GVN、SCCP)在 SSA 上写起来更简单、跑起来也更快。LLVM 与 GCC 中端都以 SSA 为核心 IR,这已经是现代编译器的事实标准。
部分冗余消除
CSE 只能消除所有路径上都出现过的重复计算。部分冗余消除(PRE, Partial Redundancy Elimination)更进一步:如果一个表达式只在部分路径上是冗余的,就在缺失的路径上"补一次",然后把汇合点之后的那次计算消掉。PRE 把 LICM 和 CSE 统一在同一个框架里,是现代编译器全局优化的主力。
死代码与不可达代码
两者常被混为一谈,其实不同:
- 死代码(Dead Code):能被执行到,但计算结果没被使用,比如没人读的赋值。DCE 依赖活跃变量分析来判定。
- 不可达代码(Unreachable Code):在控制流图里根本走不到,比如
if (false) { ... }里的块,或者return之后的语句。它由控制流分析或常量传播发现。
处理手段不同:DCE 删的是"用不上的运算",不可达代码消除删的是"到不了的路径"。
应用:为什么 -O2 能显著加速
GCC/Clang 打开 -O2 后,上面提到的优化几乎全部开启:常量传播、CSE、DCE、LICM、强度削减、有限的循环展开、PRE、以及 SSA 上的多轮清理。对典型数值代码,-O2 相对 -O0 通常有 2 到 5 倍的加速;对结构简单、循环紧凑的热点函数,效果更明显。而这些优化全部工作在 IR 上,因此换到 ARM 或 RISC-V 后端,同一套优化通道能无缝复用——这正是"机器无关"四个字的价值所在。