Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

循环优化 / 向量化 / Strength Reduction

TL;DR

循环是热代码所在——Amdahl 法则下 90% 的时间在 10% 的循环里。Compiler 把循环优化当成头等大事：LICM (Loop Invariant Code Motion) 把不变量提到循环外、循环展开 (unrolling) 减少分支开销、归纳变量强度削减 (IV strength reduction) 把乘法变成加法、SIMD 向量化把标量循环变成向量指令、Loop Fission / Fusion / Distribution 改变循环结构。所有这些 pass 都基于 loop nest tree + 支配关系 + 归纳变量 (induction variable) 分析。LLVM 用 LoopInfo、HotSpot 用 Loop Tree，Cranelift 用 ebb-based loopCFG。

一、Loop 的形式化

Natural Loop

        preheader
            ↓
       ┌→ header ←─┐
       │    ↓       │
       │   body     │  backedge
       │    ↓       │
       └─ latch ────┘
            ↓
         exit

Natural loop 的判定：

  1. 找到 back-edge u → h（h dominates u）。
  2. header h，loop body = {h} ∪ {所有能到达 u 的节点}。

这套用 支配树 (dominator tree) 算得出。LLVM LoopInfo 把所有 natural loop 算出来，构成 loop nest forest——内层循环是外层循环的子节点。

Preheader & Exit block

优化 LICM 需要 preheader（循环前的单一前驱）来放外提的指令；loop exit 块用来放"循环退出时的逻辑"。Irreducible loop（multi-entry）通常先通过 node splitting 转化成 reducible——这种"硬核" irreducible 转换很少做，Harvard 论文里 HotSpot 用 Loopify pass 处理。

二、LICM (Loop-Invariant Code Motion)

识别不变量

一个指令 x = a + b 在循环内是 invariant 的，当：

  1. 所有 operand 是常量、或定义在循环外、或定义在循环内但本身 invariant。
  2. 指令没有副作用（store、call、可能 throw）。
  3. 指令所在的 block 支配所有 loop exit——否则外提会改变"如果循环 0 次迭代就执行"的语义。
for (i = 0; i < n; i++) {
    a[i] = x + y;        // x + y 不变，LICM 提到循环外
}

→

int t = x + y;             // hoisted
for (i = 0; i < n; i++) {
    a[i] = t;
}

安全条件

支配所有 exit 这一条件容易翻车：

for (;;) {
    if (cond) break;       // exit 在 mid-loop
    a = compute_invariant();
}

compute_invariant() 所在 block 不支配 exit block（exit 在 break 之后），不能简单外提——循环可能 0 次执行 compute 后就 break。LLVM 解法是 loop rotation——把循环变成 do-while 形式，preheader 先执行一遍，保证 body 至少跑一次。

LoadLICM

load *p 在循环内、循环不变量？需要 alias analysis 证明循环内没有 store 可能改 *p。否则不能外提。这是 alias info 进入 LICM 的入口。-fstrict-aliasing 让 type-based alias analysis (TBAA) 严格起来，能更多外提。

三、归纳变量分析 (Induction Variable)

基本归纳变量

for (i = 0; i < n; i++) {
    a[i] = b[i];
}

i 是 basic IV (induction variable)：每次加常量。a[i] 的地址是 &a + i*4，是 derived IV——线性映射自基本 IV。

强度削减 (Strength Reduction)

把循环里的乘法变成加法：

int *p = a;
for (i = 0; i < n; i++) {
    *p++ = b[i];        // p 每次加 4 字节，i 加 1
}

→

i : 0, 1, 2, ..., n-1
p : a, a+4, a+8, ..., a+4*(n-1)

p 直接当 IV 用，省掉 a + i*4 的乘法。在现代 CPU 上乘法不慢，但地址计算的 IV 替换对 cache 局部性、load/store 单元利用仍有意义。LLVM 的 loop-strength-reduce pass 做这个。

Linear Function Test Replacement (LFTR)

for (i = 0; i < n; i++) {
    j = 4 * i;
}

把 i < n 替换为 j < 4 * n（用 derived IV），删掉 i。这叫 LFTR——把循环终结条件也转成新 IV 形式，彻底删掉 i 这个 IV。

四、循环展开 (Unrolling)

Fully vs Partial

// 原始
for (i = 0; i < n; i++) a[i] = b[i] + c[i];

// 完全展开
a[0] = b[0] + c[0];
a[1] = b[1] + c[1];
...
a[n-1] = b[n-1] + c[n-1];

// 部分展开（4 路）
for (i = 0; i < (n & ~3); i += 4) {
    a[i]   = b[i]   + c[i];
    a[i+1] = b[i+1] + c[i+1];
    a[i+2] = b[i+2] + c[i+2];
    a[i+3] = b[i+3] + c[i+3];
}
for (; i < n; i++) a[i] = b[i] + c[i];     // 余数处理

代价

  • 减少分支、减少 loop overhead、给指令调度更大空间。
  • 代码体积膨胀——i-cache 友好性下降。LLVM 用 trip count 和 PGO 决定展开度。
  • 完全展开（trip count 静态已知且小）：用于减少 hot loop 的总开销。

HotSpot 的 Loop Unroll

JIT 把循环编译成计数器+entry check 形式：

for (int i = 0; i < 1000; i++) {
    body
}

→ HotSpot C2 用 OSR (On-Stack Replacement) 从解释栈切到 JIT 后编译，先降速运行计数器后编译，编译时 trip count 已知就能完全展开。Rust、Go 编译器没这套 JIT 机制——只能静态 trip count 推断。

Unroll & Jam

for (i = 0; i < n; i++) {
    a[i] = f(i);
    b[i] = g(i);
}

展开外层 → 内层仍有独立 jam，组合执行 → 寄存器重用上升。工程上用得少，但 HotSpot 和 ICC 做这个。

五、SIMD 自动向量化

SIMD 指令模型

x86 AVX2：256bit 寄存器，一条指令处理 8 个 float32、4 个 float64、8 个 int32。

for (i = 0; i < n; i++) {
    c[i] = a[i] + b[i];
}

→

vmovups ymm0, [a+i]
vaddps  ymm1, ymm0, [b+i]
vmovups [c+i], ymm1

每条 vaddps 跑 8 个 float 加法。

向量化的合法性

  1. 无循环携带依赖 (loop-carried dependence)： 
    for (i = 1; i < n; i++) a[i] = a[i-1] + 1;   // 写 a[i] 依赖前次 a[i-1]，不可向量化
  2. 内存不别名：a、b、c 不重叠。LLVM 通过 noalias (C restrict)、TBAA 等机制证明。
  3. 可处理余数：n 不能被 SIMD lane 数整除，需要 mask 或 scalar tail loop。

LLVM 的 Vectorizer

  • loop-vectorize：循环级向量化，处理带 preheader 的规范循环。
  • slp-vectorizer：基本块内的 superword-level parallelism——一组标量指令有相同 op 时打包成 SIMD。

GCC、ICC、HotSpot 编译器都有等价 pass。LLVM 的向量化成本模型基于"target transform info (TTI)"——知道目标 CPU 的指令 throughput、寄存器数、掩码能力。

工程上的"反例"

// 不可向量化（Python list comprehension 编译到 C 的常翻场景）
for (i = 0; i < n; i++) {
   (bin)[i] = (a[i] > 0) ? a[i] : 0;        // select 不是分支，可向量化
}

for (i = 0; i < n; i++) {
    if (a[i] > 0) b[i] = a[i];               // 通过 mask load/store + blend 可向量化
    else b[i] = 0;
}

// 真不可向量化：间接访问
for (i = 0; i < n; i++) b[idx[i]] = a[i];    // gather/scatter，AVX2 支持但慢

Gather/Scatter 在 AVX2 起支持但 throughput 差。常规向量化偏好 unit-stride 访问。

六、其他循环 pass

Loop Fusion

for (i = 0; i < n; i++) a[i] = i;
for (i = 0; i < n; i++) b[i] = a[i] * 2;

→

for (i = 0; i < n; i++) {
    a[i] = i;
    b[i] = a[i] * 2;       // 寄存器复用 a[i]
}

前提：trip count 相同、无依赖、无副作用融合后变化。

Loop Fission (Distribution)

for (i = 0; i < n; i++) {
    a[i] = compute_a(i);
    if (cond[i]) b[i] = compute_b(i);    // 罕见分支拖累 SIMD
    c[i] = compute_c(i);
}

→

for (i = 0; i < n; i++) a[i] = compute_a(i);
for (i = 0; i < n; i++) if (cond[i]) b[i] = compute_b(i);
for (i = 0; i < n; i++) c[i] = compute_c(i);

把可向量化部分与有分支的部分拆开。

Loop Interchange

for (j = 0; j < M; j++)
    for (i = 0; i < N; i++)
        a[i][j] = ...;

→

for (i = 0; i < N; i++)
    for (j = 0; j < M; j++)
        a[i][j] = ...;

C 用行主序，外层 i 内层 j → 连续访问，cache miss 大降。但要求无依赖——若内层循环有 carried dep 这就改了语义。

Loop Rerolling

源码手写展开后重新 roll：

x = a[0] + a[1] + a[2] + a[3];

→ 重新 roll 成

for (i = 0; i < 4; i++) x += a[i];

允许后续 SIMD 看到"循环"语义重新向量化。LLVM 的 re-roll pass。不常见但 very few projects 依赖（如 BLAS 模板）。

Loop Peeling

把循环的前 k 次分出来：

for (i = 0; i < n; i++) body;

→

body;  // i = 0
for (i = 1; i < n; i++) body;

用于消除异常迭代的不变量、给后续 pass 减小分析范围（比如证明 alias、消除边界检查）。

七、工业事故：循环优化的真实翻车

GCC -fstrict-aliasing + Linux Kernel

Linux kernel 某些代码用 union 来 alias 不同类型，违反 strict aliasing。GCC 4.x 在 -O2 后默认 strict-aliasing，删掉了一些 union 重叠访问的代码 → 静默数据损坏。社区加 -fno-strict-aliasing。

LLVM Loop Unroll + 工程代码

某项目把 100MB 数组完全展开后整个 binary 爆炸（500MB+），编译器来不及反馈给用户。LLVM 加 -mllvm -max-unroll-times 上限。

ICC 的 Auto-vectorization 性能问题

ICC 自动向量化 TSVC benchmark 加速 2-5x，但当遇到包含条件分支 + 间接访问的组合时退回标量。模型本身没 bug——但用户误解"自动向量化一定生效"。Profile 显示 scalar tail 太多，需要手动加 #pragma omp simd。

八、Per-CPU 策略

x86 vs ARM vs GPU

  • x86 AVX2/AVX-512：256/512bit 寄存器，向量化带来 4-16x 加速。AVX-512 的 mask register 让条件向量化很优雅。
  • ARM NEON / SVE：NEON 128bit 固定宽度；SVE 是可变 SIMD 宽度 (128-2048 bit)，同一 binary 在不同硬件跑出 CPU 支持的 lane 数。SVE 的 whilelt 指令完美处理 tail loop。
  • GPU：PTX 的 SIMT 模型，warp 32 thread 同步执行。GPU 编译器的向量化更像是"识别_parallel pattern + memory coalescing"。

CPU Profile-Guided Vectorization

PGO 提供 trip count 分布、分支概率，编译器决定展开度和是否向量化。LLVM 的 opt -pgo 流程：

  1. 编译 -fprofile-generate 插桩
  2. 真实运行收集 trip count
  3. -fprofile-use 重编译，cost model 优化

PostgreSQL、Chromium 项目都大量用 PGO。

九、易错清单

  1. 浮点循环不能重排结合：sum += a[i] 循环展开后并行加会破坏浮点结合律。-ffast-math 或 Rust fadd fast 才允许。
  2. 循环边界 n 是循环内修改的全局：compile 期 trip count 推断错；向量化时会死。
  3. pointer alias 验证不严：restrict 错放数组会让无 alias 假设错。Rust 的 ownership 模型保证 &mut 唯一 → Rust 默认无 alias，向量化比 C 容易。
  4. OSR 与 Retry Budget：HotSpot 在低层级 JIT 失败时 deopt，编译开销大。多核 CPU 上常看到 "tiered compile lag"。
  5. SIMD 的 tail loop：标量 tail 仍是开发者看到加速不到预期的真凶，应该看 asm 输出，确认 tail。

这一章带走的东西

  1. LICM 是最常用循环优化，安全条件是支配所有 exit。
  2. Induction Variable 强度削减：把乘法降级成加法，是循环中精度换算术的经典。
  3. 循环展开要配 PGO，盲目完全展开炸 depolar i-cache、binary 体积。
  4. SIMD 向量化靠无循环携带依赖 + 无 alias + trip count 信息，三者缺一编译器保守放弃。
  5. Loop Fusion / Fission / Interchange 改循环结构——编译器叫这种 "polyhedral optimization"，工程上在 ML 编译器（TVM、XLA、IREE）用得最重。

下一节 → Inline / IPA / escape analysis