1 / 4概念
Loop Transformations
循环是 ILP 的主要来源,也是寄存器压力与缓存缺失的主要来源。循环变换在不改变语义的前提下重排迭代,把独立的操作暴露给编译器或硬件。读完应能判断一次展开、流水或分块是否合法、是否划算,以及为什么依赖分析是这一切的前提。
1 概念
1.1 一句话定义
循环变换是一组保持语义的迭代空间重写,包括展开、软件流水、交换、分块、融合、分裂与倾斜,用来提高 ILP、降低循环开销或改善局部性。
1.2 它解决什么问题
- 循环开销:每次迭代的分支、比较与自增占掉可观指令数。
- 短基本块:循环体太小,调度窗口填不满,硬件看不到跨迭代并行。
- 循环携带依赖:累加器与递推把迭代串成一条长链,限制并行度。
- 缓存缺失:跨步访问与大工作集导致复用差,算力被访存拖住。
1.3 不属于本页的内容
| 主题 | 去哪 |
|---|---|
| VLIW 指令打包 | VLIW and Static ILP |
| 向量化与 SIMD | Data-Level Parallelism |
| 缓存替换与预取 | Memory Hierarchy → Caches |
| 乱序调度 | Dynamic Scheduling |
1.4 关键术语
| 术语 | 含义 | 容易混淆的点 |
|---|---|---|
| 展开 | 复制循环体若干次 | 不是向量化 |
| 软件流水 | 让不同迭代的不同阶段重叠 | 不是硬件流水线 |
| 模调度 | 求最小启动间隔的软件流水算法 | 不是循环展开 |
| 启动间隔 II | 稳定状态下两次迭代启动的间隔 | 不是延迟 |
| 序言/尾声 | 填充与排空流水线的代码 | 不是异常处理 |
| 分块 | 把迭代空间切成适合缓存的块 | 不是循环展开 |
| 倾斜 | 平移迭代坐标以改变依赖距离 | 不是循环分裂 |
2 机制
2.1 心智模型
循环变换是在迭代空间里重新排座位:合法的前提是不拆散有依赖的迭代对,划算的前提是省下的停顿大于增加的寄存器与代码。 变换只改执行顺序,不改计算结果;依赖分析是许可证,性能模型是预算表。
2.2 机制拆解
- 展开:把循环体复制 k 次,减少分支与自增,暴露跨迭代的独立操作;需要余数循环与更多寄存器。
- 软件流水:把不同迭代的不同阶段重叠,形成稳定状态;模调度求最小启动间隔。
- II 下界:
II = max(ResMII, RecMII),前者由每周期可用单元数决定,后者由依赖环的延迟与距离决定。 - 分块与条带挖掘:把大循环切成适合缓存或向量的块,条带挖掘为向量化准备连续片段。
- 交换与倾斜:交换内外层顺序改善步长与局部性;倾斜平移迭代坐标,让依赖距离变正,从而允许交换或并行。
- 融合与分裂:合并循环以共享数据,拆分循环以降低寄存器压力或暴露并行。
- 依赖分析:GCD 测试、Banerjee 测试与多面体模型;
restrict与ivdep是给编译器的别名承诺。
2.3 完整枚举
| 变换 | 改变什么 | 合法性条件 | 主要收益 | 主要代价 |
|---|---|---|---|---|
| 展开 | 循环体份数与步长 | 边界可划分,并行需可重命名 | 减少分支、增加 ILP | 代码膨胀、寄存器压力 |
| 软件流水 | 迭代的启动时间 | 依赖距离与资源允许 | 稳定状态高吞吐 | 序言尾声、寄存器压力 |
| 交换 | 内外层顺序 | 依赖方向允许 | 步长与局部性 | 可能破坏原有复用 |
| 分块 | 迭代空间划分 | 块内依赖不跨块违例 | 缓存与 TLB 复用 | 边界处理复杂 |
| 融合 | 多个循环合一 | 无反向依赖 | 数据复用、减少遍历 | 寄存器压力上升 |
| 倾斜 | 迭代坐标平移 | 保持依赖关系 | 使交换或并行合法 | 索引计算复杂 |
2.4 关键数字与复杂度
| 指标 | 量级 | 说明 |
|---|---|---|
| 展开因子 | 2–8 | 受寄存器与 i-cache 限制 |
| 启动间隔 II | 1–数十周期 | 由资源与递归约束决定 |
| 代码增长 | 每翻倍约 10–30% | 依循环体大小变化 |
| L1i | 32–64 KB | 展开过度会挤出指令 |
| 缓存行 | 64 B | 分块应围绕行与组相联设计 |
| 依赖测试 | 多项式到指数 | 多面体分析更精确但更慢 |
3 实践
3.1 最小示例
// 展开前:一条依赖链,浮点加法延迟 4 周期,II 至少 4。
for (int i = 0; i < n; i++) s += a[i];
// 展开后:四个累加器打断循环携带依赖,II 可降到 1,最后再合并。
for (int i = 0; i + 3 < n; i += 4) {
s0 += a[i]; s1 += a[i + 1];
s2 += a[i + 2]; s3 += a[i + 3];
}
s = (s0 + s1) + (s2 + s3);
四个累加器把一条长为 n 的依赖链拆成四条短链,稳定状态下每个周期都能启动一次加法。余数元素要另写循环处理;若 n 很小,序言与收尾开销可能超过收益。
3.2 常用操作与参数
| 操作 | 参数 | 说明 |
|---|---|---|
| 指定展开 | #pragma unroll、-funroll-loops | 让编译器按因子展开 |
| 声明无别名 | restrict | 承诺指针不重叠,违反即未定义行为 |
| 忽略依赖 | #pragma GCC ivdep | 仅在确知无依赖时使用 |
| 指定目标 | -march、-mtune | 影响可用指令与调度模型 |
| 设分块尺寸 | tile 大小 | 围绕缓存容量与相联度 |
| 查看报告 | -Rpass、-Rpass-analysis | 确认变换是否发生及原因 |
3.3 标准流程
- 用 profiler 找到热点循环,记录基线 IPC 与 miss。
- 做依赖与别名分析,确认变换合法。
- 选择变换:先降开销,再提 ILP,最后调局部性。
- 估算寄存器、代码体积与序言开销是否可接受。
- 实现变换并保留余数、边界与短循环路径。
- 用不同输入规模做正确性测试,再复测性能。
3.4 与相邻技术的组合
展开与软件流水给 VLIW 的静态调度提供可填充的 bundle;条带挖掘让连续元素进入同一向量寄存器;分块与预取配合,把带宽留给真正需要的数据;循环分裂与融合改变可并行粒度,但需同步与数据划分。
3.5 选型维度
| 循环类型 | 首选 | 理由 |
|---|---|---|
| 计算密集、无依赖 | 展开 + 软件流水 | 提高发射密度 |
| 内存密集、可分块 | 分块 + 交换 | 提高缓存复用 |
| 归约 | 多累加器展开 | 打断循环携带依赖 |
| 短 trip count | 不展开或轻量展开 | 序言开销大于收益 |
3.6 决策规则
- 合法性先于收益:任何依赖违例都会产生错误结果,性能无从谈起。
- 先看瓶颈:分支多则展开,延迟链长则多累加器,缺失高则分块。
- 展开因子应由寄存器预算与 i-cache 容量共同约束。
3.7 替代方案对比
| 方案 | 优势 | 代价 | 适用 |
|---|---|---|---|
| 手工展开 | 可控、可读 | 易错、难维护 | 关键内核 |
| 编译器自动展开 | 无源码改动 | 受启发式限制 | 通用代码 |
| SIMD intrinsics | 明确利用数据并行 | 可移植性差 | 向量内核 |
| 算法重写 | 根治依赖与访存 | 设计成本高 | 长期演进 |
3.8 何时不该用
- 迭代次数很小,序言、尾声与余数处理会吃掉收益。
- 存在不可分析别名或不可约控制流,变换无法证明合法。
- 寄存器压力已高,展开会引发溢出并抵消 ILP 收益。
- 循环已受内存带宽限制,提高 ILP 不会缩短时间。
4 边界
4.1 典型故障
| 症状 | 根因 | 处理 |
|---|---|---|
| 结果错 | 忽略了循环携带依赖或别名 | 回到依赖分析,去掉 ivdep |
| 性能反降 | 寄存器溢出或 i-cache 抖动 | 降低展开因子 |
| 小规模输入变慢 | 序言与余数开销占比高 | 保留简单循环分支 |
| 分块无收益 | tile 尺寸与缓存不匹配 | 按容量与相联度重算 |
| 边界越界 | 余数或尾部处理错 | 用 i + 3 < n 形式重写 |
4.2 反模式
| 做法 | 后果 | 替代 |
|---|---|---|
| 盲目展开 | 代码膨胀、寄存器溢出 | 先测瓶颈再定因子 |
无依据加 restrict | 别名时产生错误结果 | 用编译器分析或改类型 |
| tile 越大越好 | 超出缓存容量,抖动加剧 | 按工作集与相联度定尺寸 |
4.3 可观测信号
perf stat 的 IPC、L1/L2 miss、i-cache miss 与 branch miss;llvm-mca 可估算展开后的吞吐与瓶颈单元;-Rpass=loop-unroll 与 -Rpass-analysis=loop-vectorize 显示编译器是否执行变换及拒绝原因;反汇编中的溢出与栈访问可确认寄存器压力。
4.4 安全 / 性能 / 一致性边界
- 正确性:别名与依赖是硬约束,
restrict与ivdep是承诺而非优化提示,违反即未定义行为。 - 性能:变换只改变指令与访存的排列,不改变算法复杂度;内存带宽受限时收益有限。
- 安全:常数时间代码不应因展开或分块引入秘密相关的访存与分支模式。