45. 编译器优化与中间表示：SSA、内联与循环优化

1. 优化发生在哪里

现代编译器（以 LLVM/Clang 为代表）把优化集中在中端，靠一套**与源语言和目标机器都解耦的中间表示（Intermediate Representation，IR）**承载所有变换。前端负责「源语言 → IR」，中端在 IR 上反复跑优化 pass，后端负责「IR → 目标机器码」。

源码 ──前端──▶ AST ──▶ IR(LLVM IR) ──中端优化 pass──▶ IR' ──后端──▶ 汇编/机器码
                     ▲                                      ▲
                语义分析与类型检查                        指令选择、寄存器分配

这种分层的好处是：N 种语言 × M 种目标机器，只需 N 个前端 + M 个后端，中间的优化 pass 全部复用。

2. 中间表示的层次

2.1 从 AST 到三地址码

抽象语法树（AST）保留了语法结构，但不适合做机器无关优化。降级的第一步通常转成三地址码（Three-Address Code，TAC）：每条指令最多一个运算符、三个操作数。

# 源：x = a * b + c * d
t1 = a * b
t2 = c * d
x  = t1 + t2

2.2 LLVM IR 形态

LLVM IR 是静态单赋值（见第 3 节）的三地址码，有文本与位码两种形式：

; 函数签名：i32 参数，返回 i32
define i32 @f(i32 %a, i32 %b, i32 %c, i32 %d) {
entry:
  %t1 = mul i32 %a, %b
  %t2 = mul i32 %c, %d
  %x  = add i32 %t1, %t2
  ret i32 %x
}

2.3 基本块与控制流图

优化以基本块（Basic Block）为单位——块内无分支、无跳入跳出的中间点。基本块用边连接成控制流图（Control Flow Graph，CFG），所有数据流分析都在 CFG 上做。

       ┌─────────┐
       │ entry   │
       └────┬────┘
        ┌───┴───┐
        ▼       ▼
    ┌───────┐ ┌───────┐
    │ then  │ │ else  │
    └───┬───┘ └───┬───┘
        └───┬─────┘
            ▼
        ┌───────┐
        │ merge │
        └───────┘

3. SSA 形式

3.1 静态单赋值

SSA（Static Single Assignment） 要求每个变量只被赋值一次。原始代码里的多次赋值会被拆成带下标的多个版本：

# 非 SSA
x = 1
x = x + 1
y = x * 2

# SSA 化
x0 = 1
x1 = x0 + 1
y0 = x1 * 2

SSA 的威力在于：每个变量的定义点唯一，因此「使用了哪个值」一目了然，常量传播、CSE、死代码消除都变成简单的图遍历。

3.2 φ 函数

分支合流时，同一个变量可能有多个来源，SSA 用 φ 函数在合流点「选择」来自哪个前驱的值：

      if (c)
     /      \
  x1 = 1   x2 = 2
     \      /
   x3 = φ(x1, x2)   ; 来自 then 分支取 x1，else 分支取 x2

merge:
  %x3 = phi i32 [ %x1, %then ], [ %x2, %else ]

φ 函数不是真实指令，后端在退出 SSA（out-of-SSA）时会插入复制指令或直接消除。

3.3 支配树

支配（Dominance） 关系是 SSA 构造的基础：节点 A 支配 B，指从入口到 B 的每条路径都经过 A。

• 支配树（Dominator Tree）：每个节点指向其直接支配者。
• 支配边界（Dominance Frontier）：φ 函数恰好插在「定义了变量的块的支配边界」上。

算法：构造 SSA 的两步
1. 计算支配树与支配边界（Lengauer-Tarjan 算法，近似线性）
2. 在每个变量的支配边界处插入 φ 函数，再重命名变量

4. 数据流分析与经典优化

数据流分析在 CFG 上迭代求解「到达定值」「活跃变量」「可用表达式」等信息，是大多数优化的前置。

4.1 常量传播与折叠

# 常量传播（Constant Propagation）
x = 5
y = x + 3      →   y = 8
z = y * 2      →   z = 16

# 常量折叠（Constant Folding）
a = 3 * 4      →   a = 12

4.2 死代码消除

死代码消除（Dead Code Elimination，DCE） 删除「结果从未被使用」的指令。配合活跃变量分析：若一条赋值的目标变量在后续路径上都不活跃，即可删除。

x = compute()   ; x 从未被使用
y = 1           →   删除 x = compute()

4.3 公共子表达式消除

CSE（Common Subexpression Elimination） 复用重复计算。在 SSA 下等价于全局值编号（Global Value Numbering，GVN）：

a = b + c
d = b + c      →   d = a   ; 复用 a

4.4 主要优化对照

5. 内联

5.1 为什么内联是「优化之母」

内联（Inlining） 把被调函数的函数体直接展开到调用点。它本身不减少指令，却打开了跨函数优化的窗口：常量实参可传播、返回值可消除、循环可跨函数外提。没有内联，几乎所有过程间优化都无从谈起。

# 内联前
int square(int x) { return x * x; }
int y = square(5);

# 内联后（常量传播接管）
int y = 5 * 5;   →   int y = 25;

5.2 代价模型

内联不能无脑做——代码膨胀会撑爆指令缓存（I-Cache）。编译器用**代价模型（Cost Model）**权衡：

内联收益 ≈ 省下的调用开销 + 暴露出的优化机会
内联代价 ≈ 展开后新增的指令数 × 命中频率

常见阈值（示意）：
- 函数体小于 ~25 条指令：总是内联
- 单次调用点、函数体中等：倾向内联
- 热点循环内的调用：提高内联预算
- 递归/巨型函数：拒绝内联

GCC 用 -finline-limit，LLVM 用 inline-threshold（默认 225）控制。always_inline / noinline 属性可覆盖启发式：

static inline __attribute__((always_inline)) int fast_add(int a, int b) {
    return a + b;
}
__attribute__((noinline)) void big_slow_path(void) { /* 巨型冷路径 */ }

5.3 内联的边界

• 虚函数：需先去虚拟化（devirtualization）才能内联。
• 跨编译单元：需 LTO（Link-Time Optimization）或 -flto。
• 递归：只能部分展开或完全拒绝。
• 调试友好性：内联破坏调用栈，调试构建常关闭。

6. 循环优化

循环占据程序运行时间的大头，是优化的重中之重。

6.1 循环不变量外提（LICM）

把循环体内「结果不随迭代改变」的计算移到循环外：

# 优化前
for i in 0..n:
    t = a * b          ; a、b 在循环内不变
    arr[i] = t + i

# LICM 后
t = a * b
for i in 0..n:
    arr[i] = t + i

6.2 循环展开与流水线

循环展开（Loop Unrolling） 把多次迭代合并，减少循环控制开销、增加指令级并行：

# 展开因子 4
for i in 0..n step 4:
    body(i); body(i+1); body(i+2); body(i+3)

软件流水（Software Pipelining） 更进一步，让不同迭代的指令重叠执行，掩盖访存延迟。

6.3 循环变换族

6.4 自动向量化

把标量循环转成 SIMD 指令，需满足无循环携带依赖且访存连续：

// 可向量化：每次迭代独立
for (int i = 0; i < n; i++) c[i] = a[i] + b[i];

// 不可向量化：依赖前一次结果
for (int i = 1; i < n; i++) a[i] += a[i-1];   // 循环携带依赖

查看是否向量化：clang -Rpass=loop-vectorize、gcc -fopt-info-vec。

7. 寄存器分配

IR 里变量无限多，物理寄存器有限（x86-64 通用寄存器仅 16 个）。寄存器分配决定「哪些变量驻留寄存器、哪些溢出（spill）到栈」。

7.1 图着色分配

把「同时活跃的变量」连边，构成冲突图（Interference Graph）；用 K 种颜色（K = 寄存器数）着色，相邻节点不同色。经典算法 Chaitin-Briggs 的步骤：

1. 构造冲突图（基于活跃变量分析）
2. 化简：反复删除度数 < K 的节点，压栈
3. 若图空 → 直接分配；否则选择溢出候选
4. 出栈并着色，冲突则真正溢出

7.2 线性扫描

图着色精度高但慢。线性扫描（Linear Scan） 按活跃区间端点排序，一趟扫描完成分配，被 JIT 编译器（如 V8、HotSpot）广泛采用：

8. 动手：读一段 LLVM IR

# 生成未优化的 IR
clang -S -emit-llvm -O0 -o - sum.c
# 生成优化后的 IR
clang -S -emit-llvm -O2 -o - sum.c

; -O2 下，函数被内联、常量传播后可能只剩一条 ret
define i32 @main() {
entry:
  %r = add nsw i32 25, 0    ; 常量折叠结果
  ret i32 %r
}

用 opt -passes='function(mem2reg,instcombine,gvn)' 可单独跑指定 pass 观察每步变化；llc 则把 IR 降级到目标汇编。理解这套工具链，才能真正读懂「编译器到底对你的代码做了什么」。

9. 小结

编译器优化的主线是：前端产出 IR → 中端在 SSA 上跑数据流分析驱动的变换 → 后端做指令选择与寄存器分配。SSA 用「单赋值 + φ 函数」把数据依赖显式化，使常量传播、DCE、CSE 都退化为图遍历；内联是跨函数优化的钥匙，代价模型防止代码膨胀；循环优化（LICM、展开、分块、向量化）针对运行热点；寄存器分配在冲突图上做 K 着色或用线性扫描求快。这些机制建立在前端语法分析之上，最终生成的目标码又回到指令集与流水线层面执行。

参考文章

• 编译原理基础：https://plumephp.com/cs-compiler-basics/
• 形式语言与自动机：https://plumephp.com/cs-formal-languages-automata/
• 计算机组成与指令集：https://plumephp.com/cs-computer-organization/