在现代程序中，循环结构往往占据了90%以上的执行时间。从科学计算的矩阵运算到深度学习的张量操作，从数据库的查询处理到图形渲染的像素遍历，循环无处不在。LLVM的循环优化基础设施代表了编译器优化技术的最高水平，它不仅需要精确的程序分析，还要深入理解现代处理器的微架构特性。本章将深入探讨LLVM如何通过LoopInfo、ScalarEvolution、向量化器等组件构建起一套完整的循环优化体系，以及这个体系如何随着硬件架构的演进而不断进化。
LLVM的LoopInfo分析pass是所有循环优化的基石。它负责从控制流图（CFG）中识别自然循环（natural loops），并构建循环嵌套森林（loop nest forest）。
循环的定义与识别
在LLVM中，一个自然循环必须满足以下条件：
+----> Header <----+
| | |
| v |
| Body1 |
| | |
| v |
| Body2 ------+
| |
| v
+---- Exit Block
LoopInfo使用深度优先搜索（DFS）识别回边，然后通过自然循环算法构建循环结构：
循环的规范化
LLVM倾向于将循环转换为规范形式（canonical form），这简化了后续优化：
ScalarEvolution（SCEV）是LLVM中最复杂也最强大的分析之一。它将循环中的表达式建模为递归序列，使编译器能够推理循环的迭代次数、数组访问模式等关键信息。
SCEV表达式的代数系统
SCEV定义了一套完整的表达式系统：
归纳变量的识别
考虑一个简单的循环：
for (int i = 0; i < n; i += 2) {
a[i] = b[i] + c[i];
}
SCEV将变量i建模为加法递归： \(\text{SCEV}(i) = \{0, +, 2\}_{\text{loop}}\)
这表示i从0开始，每次迭代增加2。对于更复杂的情况，如二次递归：
int sum = 0;
for (int i = 0; i < n; i++) {
sum += i; // sum = 0 + 1 + 2 + ... + (n-1)
}
SCEV表示为： \(\text{SCEV}(sum) = \{0, +, \{0, +, 1\}_{\text{loop}}\}_{\text{loop}} = \frac{n(n-1)}{2}\)
循环次数的计算
SCEV的核心能力之一是计算循环的迭代次数（trip count）。对于条件 i < n，SCEV需要求解不等式：
\(\{start, +, step\}_{\text{loop}} < bound\)
这涉及到：
循环优化的正确性依赖于精确的内存依赖分析。LLVM提供了多层次的分析：
Loop Access Analysis (LAA)
LAA负责分析循环中的内存访问模式，判断是否存在依赖关系：
运行时依赖检查
当静态分析无法确定时，LLVM会生成运行时检查代码：
; 检查数组是否重叠
%overlap = icmp ult %ptr1.end, %ptr2.begin
%safe = or %overlap, %no_alias_other_check
br i1 %safe, label %vector.loop, label %scalar.loop
LLVM的Loop Vectorizer在2012年首次引入，经过十年演进已成为产品级的向量化器。其核心设计包括：
合法性分析（Legality Analysis）
向量化器首先判断循环是否可以安全地向量化：
成本模型（Cost Model）
向量化器使用精细的成本模型决定是否向量化以及向量化因子（VF）：
\[\text{Cost} = \frac{\text{ScalarCost} \times \text{TripCount}}{\text{VF}} + \text{VectorOverhead}\]成本计算考虑：
向量化策略
Loop Vectorizer支持多种向量化策略：
VPlan（Vectorization Plan）是LLVM在2017年引入的新架构，旨在解决Loop Vectorizer的局限性：
VPlan的设计动机
传统Loop Vectorizer的问题：
VPlan IR
VPlan引入了专门的中间表示：
VPlan for VF=4:
vector.ph:
EMIT %vec.ind = phi <0, 1, 2, 3>
vector.body:
WIDEN %load = load %ptr
WIDEN %add = add %load, %vec.ind
WIDEN store %add, %ptr
EMIT %vec.ind.next = add %vec.ind, <4, 4, 4, 4>
多版本代码生成
VPlan支持生成多个版本的向量化代码：
; 运行时选择最优版本
if (trip_count > 64 && aligned(ptr)) {
vector_loop_vf8_unrolled();
} else if (trip_count > 16) {
vector_loop_vf4();
} else {
scalar_loop();
}
Reduction识别与优化
LLVM能识别多种reduction模式：
// 加法reduction
for (int i = 0; i < n; i++)
sum += a[i];
// 最大值reduction
for (int i = 0; i < n; i++)
max = (a[i] > max) ? a[i] : max;
// 逻辑reduction
for (int i = 0; i < n; i++)
found = found || (a[i] == target);
向量化器生成高效的reduction代码：
; 水平加法reduction
%vec.sum = call <4 x float> @llvm.vector.reduce.fadd(<4 x float> %vec)
谓词向量化（Predicated Vectorization）
对于包含条件执行的循环：
for (int i = 0; i < n; i++) {
if (a[i] > 0)
b[i] = sqrt(a[i]);
}
生成masked向量指令：
%mask = fcmp ogt <4 x float> %a, zeroinitializer
%sqrt = call <4 x float> @llvm.masked.sqrt(<4 x float> %a, <4 x i1> %mask)
Polly将循环nest建模为整数多面体，使用整数线性规划进行优化。
SCoP（Static Control Parts）识别
Polly只能优化满足特定条件的代码区域：
for (i = c1; i < c2*n + c3; i += c4)A[c1*i + c2*j + c3]多面体表示
循环嵌套被表示为迭代空间多面体：
for (i = 0; i < N; i++)
for (j = 0; j < M; j++)
A[i][j] = B[i][j] + C[i][j];
| 迭代空间：${(i,j) | 0 \leq i < N, 0 \leq j < M}$ |
依赖多面体
数据依赖表示为多面体间的关系： \(\text{Dep} = \{S_1[i_1,j_1] \to S_2[i_2,j_2] | \text{constraints}\}\)
循环变换
Polly支持复杂的循环变换：
// 优化后：列优先访问
for (j = 0; j < M; j++)
for (i = 0; i < N; i++)
sum += A[j][i]; // 缓存友好
2. **循环分块（Loop Tiling）**
```c
// 优化后的分块代码
for (ii = 0; ii < N; ii += TILE)
for (jj = 0; jj < M; jj += TILE)
for (i = ii; i < min(ii+TILE, N); i++)
for (j = jj; j < min(jj+TILE, M); j++)
C[i][j] += A[i][k] * B[k][j];
调度优化
Polly使用isl（Integer Set Library）进行调度优化：
尽管理论优美，Polly在实践中遇到诸多挑战：
Tobias Grosser在2019年的反思中指出，Polly更适合作为研究工具而非产品级优化器。
循环分块的精细调优
现代处理器的多级缓存要求精心设计的分块策略：
// 三级分块for矩阵乘法
for (i2 = 0; i2 < N; i2 += L3_TILE)
for (j2 = 0; j2 < N; j2 += L3_TILE)
for (k2 = 0; k2 < N; k2 += L3_TILE)
// L2 cache blocking
for (i1 = i2; i1 < min(i2+L3_TILE,N); i1 += L2_TILE)
for (j1 = j2; j1 < min(j2+L3_TILE,N); j1 += L2_TILE)
for (k1 = k2; k1 < min(k2+L3_TILE,N); k1 += L2_TILE)
// L1 cache blocking
for (i0 = i1; i0 < min(i1+L2_TILE,N); i0 += L1_TILE)
for (j0 = j1; j0 < min(j1+L2_TILE,N); j0 += L1_TILE)
for (k0 = k1; k0 < min(k1+L2_TILE,N); k0 += L1_TILE)
// Register blocking
for (i = i0; i < min(i0+L1_TILE,N); i++)
for (j = j0; j < min(j0+L1_TILE,N); j++)
for (k = k0; k < min(k0+L1_TILE,N); k++)
C[i][j] += A[i][k] * B[k][j];
预取优化
LLVM生成预取指令优化内存访问：
; 软件预取
call void @llvm.prefetch(i8* %ptr, i32 0, i32 3, i32 1)
; 参数：地址、读/写、局部性、缓存类型
从SSE到AVX-512
LLVM需要适配不断演进的SIMD指令集：
向量化成本模型的调整
不同指令集的成本差异巨大：
; AVX2的FMA指令 - 1个周期延迟
%fma = call <8 x float> @llvm.fma.v8f32(<8 x float> %a, <8 x float> %b, <8 x float> %c)
; 模拟FMA - 2个周期延迟
%mul = fmul <8 x float> %a, %b
%add = fadd <8 x float> %mul, %c
循环展开的策略
循环展开需要平衡多个因素：
LLVM的展开启发式：
; pragma控制的展开
!llvm.loop !{!0, !1}
!0 = !{!"llvm.loop.unroll.count", i32 4}
!1 = !{!"llvm.loop.vectorize.width", i32 8}
谓词执行与无分支代码
生成无分支代码减少分支预测失败：
; 条件选择代替分支
%cmp = icmp sgt i32 %a, %b
%max = select i1 %cmp, i32 %a, i32 %b
ScalarEvolution基于Chains of Recurrences (CR)理论，这是由Robert van Engelen等人在2001年提出的。
CR的形式化定义
一个CR表达式定义为： \(\{f_0, \oplus, f_1, \oplus, ..., f_k\}_n\)
其中：
闭式求解
对于简单的加法递归： \(\{a, +, b\}_n^i = a + b \cdot i\)
对于二次递归： \(\{a, +, \{b, +, c\}_n\}_n^i = a + b \cdot i + c \cdot \frac{i(i-1)}{2}\)
一般的k阶多项式递归： \(\{a_0, +, \{a_1, +, \{a_2, +, ...\}_n\}_n\}_n^i = \sum_{j=0}^{k} a_j \binom{i}{j}\)
可分析的模式
SCEV能够精确分析：
局限性
SCEV无法处理：
符号范围分析
SCEV维护符号表达式的范围信息：
%i = {0,+,1}<%loop>
%j = {0,+,2}<%loop>
%sum = {0,+,{1,+,2}<%loop>}<%loop>
Ranges:
%i: [0, n)
%j: [0, 2n)
%sum: [0, n*(2n-1)/2]
NSA（No-Signed-Wrap）和NUW（No-Unsigned-Wrap）标记
SCEV使用这些标记来推断更精确的信息：
%add = add nsw i32 %i, 1 ; 有符号不溢出
%mul = mul nuw i32 %j, 2 ; 无符号不溢出
与SMT求解器的集成
复杂的约束可能需要SMT求解器（如Z3）：
Query: Is (i * 4 + j * 8) < array_size for all valid i,j?
Constraints:
0 <= i < n
0 <= j < m
n * m <= 1024
缓存与规范化
SCEV使用激进的缓存策略：
复杂度管理
SCEV分析的时间复杂度控制：
// 深度限制
if (Depth > MaxSCEVAnalysisDepth)
return getUnknown(V);
// 操作数限制
if (Ops.size() > MaxSCEVOperands)
return getUnknown(V);
Tobias Grosser在2011年的博士论文中首次将多面体模型引入LLVM。他的愿景是将GCC的Graphite和IBM XL编译器的先进循环优化带到LLVM。
关键贡献：
反思与教训： 2019年，Grosser在LLVM开发者会议上坦言：”Polly证明了多面体模型的威力，但也暴露了其在真实世界应用中的局限。未来的方向应该是将多面体技术的精华融入主流优化管道。”
Arnold Schwaighofer在Apple工作期间（2012-2015）主导了Loop Vectorizer的开发，这成为LLVM向量化能力的转折点。
里程碑时刻：
Michael Zolotukhin在2014-2017年间对LLVM的循环优化基础设施进行了系统性改进。
主要贡献：
本章深入探讨了LLVM循环优化的核心技术。我们看到了：
LoopInfo和ScalarEvolution构成了循环分析的数学基础，通过Chains of Recurrences理论提供了强大的归纳变量分析能力
Loop Vectorizer的演进展示了工程实践的迭代：从简单的内层循环向量化，到VPlan架构的引入，体现了在复杂性和实用性之间寻找平衡
Polly项目虽然未能成为主流，但其多面体模型的探索为循环优化提供了理论上界，其经验教训影响了后续的设计决策
硬件协同优化的重要性：现代循环优化必须深入理解缓存层次、SIMD指令集、分支预测等微架构特性
数学与工程的结合：ScalarEvolution展示了如何将抽象的数学理论（CR代数）转化为实用的编译器组件
关键公式汇总：
习题5.1：循环识别 给定以下CFG，识别其中的自然循环并指出loop header和back edge：
BB1 → BB2 → BB3 → BB4
↓ ↓ ↓
BB5 ← BB6 ← BB7
↓
BB8
Hint: 首先构建支配树，然后查找back edges
习题5.2：SCEV表达式 将以下循环中的变量i和sum表示为SCEV表达式：
int sum = 10;
for (int i = 1; i <= n; i *= 2) {
sum = sum + i;
}
Hint: 注意这是几何级数而非算术级数
习题5.3：向量化合法性 判断以下循环是否可以安全向量化，并说明原因：
for (int i = 1; i < n; i++) {
a[i] = a[i-1] + b[i];
}
Hint: 考虑跨迭代的数据依赖
习题5.4：循环分块优化 设计一个循环分块策略，优化以下矩阵转置操作。假设矩阵大小为1024×1024，L1 cache为32KB，cache line为64字节：
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
B[j][i] = A[i][j];
Hint: 计算合适的tile大小以最大化cache利用率
习题5.5：SCEV闭式求解 推导以下嵌套循环中sum的闭式解：
int sum = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
sum += i * j;
}
}
Hint: 使用二项式系数和组合恒等式
习题5.6：向量化成本模型 设计一个成本模型，决定是否向量化以下包含条件的循环。假设：
for (int i = 0; i < n; i++) {
if (a[i] > threshold)
b[i] = a[i] * 2;
}
Hint: 考虑分支预测失败的惩罚
习题5.7：Polly多面体优化（开放题） 讨论为什么以下现实代码难以用多面体模型优化，并提出改进方案：
for (int i = 0; i < n; i++) {
int idx = index_array[i];
if (idx >= 0 && idx < m) {
result[idx] += data[i] * weights[idx];
}
}
陷阱：过度依赖SCEV的trip count计算
; SCEV可能返回Conservative的结果
for (unsigned i = n; i != 0; i--) // SCEV可能无法计算exact trip count
调试技巧：
-analyze -scalar-evolution查看SCEV分析结果hasLoopInvariantBackedgeTakenCount()返回值陷阱：盲目向量化可能降低性能
// 稀疏访问模式
for (int i = 0; i < n; i += 32)
sum += a[i]; // 向量化反而慢
调试技巧：
-Rpass=loop-vectorize -Rpass-analysis=loop-vectorize陷阱：优化顺序影响最终效果
LICM → Unroll → Vectorize // 可能错过向量化机会
Vectorize → LICM → Unroll // 可能更好
调试技巧：
-debug-pass=Structure查看pass执行顺序陷阱：过于保守的别名分析阻止优化
void foo(int* restrict a, int* restrict b) {
// 即使有restrict，LLVM可能仍然保守
}
调试技巧：
__builtin_assume_aligned提供对齐信息restrict关键字或noalias属性