【硬核体系结构与编译器技术】编译器的降维打击——指令调度与循环展开

2026-06-02 13 min

这份笔记源自于(99+ 封私信) 【硬核体系结构与编译器技术01】2. 编译器的降维打击：指令调度和循环展开的初步分析 - 知乎，目前是通过 AI 初步整理，加上作者的一些个人理解和修改整理得到的。主要脉络如下：

在前一篇文章的基础上（NPU在硬件设计上面临的功耗与面积困境），引出编译器。
先补充介绍硬件调度的缺陷。
后介绍编译器针对这些缺陷的解决方法。

概述

面对指令级并行（ILP）中的数据相关问题，硬件的动态调度（乱序执行）存在视野窄、时间仓促等物理限制。编译器则利用“静态编译”阶段的上帝视角和充裕时间，通过强度削弱、指令调度、循环展开三大招式，将硬件不友好的代码重排为硬件友好的形式，从而白嫖大量性能。

编译器的定位：人机桥梁

核心功能：将人类可读的高级语言（如.c/.cpp）无损地“翻译”成底层硬件能直接执行的二进制机器码（ISA，指令集架构）。
解释型语言：解释器/虚拟机模拟了底层硬件，将源码转译为底层能够直接识别的形式。
关于解释器的补充：
旁注：解释器的“套娃” 有意思的是，解释器本身也是由源代码编写出来的程序，它同样需要经过 C/C++ 编译器转译，才能变成特定硬件平台上的二进制可执行文件。只是，这个解释器承载的功能不再是直接处理你的业务逻辑，而是在操作系统之上“模拟”出一个虚拟的硬件环境。这个虚拟硬件接收你的输入，并在底层物理硬件上产生对应的累积效果（Side Effect，副作用，比如：点亮网卡的一个端口、在屏幕上输出一段字符）。这些最终的物理副作用，才是程序员原本的真实意图。
本质：将人类逻辑降维成枯燥但高效的二进制表示。

硬件调度的底线与限制

数据相关（RAW，写后读）是逻辑上客观存在、无法直接抹除的真相关问题，硬件发展出了旁路转发（Forwarding）和乱序执行（Out of Order, OoO）来动态解决，但硬件调度有沉重的包袱：

必须绝对兜底：代码再烂也不能算错（如1994年Intel奔腾浮点除法Bug，代价惨痛）。
“高度近视”：乱序窗口（ROB）有限，遇到分支跳转就看不清后面的代码。
“极度仓促”：必须在纳秒/皮秒级的时间内当场决定指令去向，无法做深度推演。

编译器的三大优化策略

硬件的动态调度非常凶险且视野狭窄，相比之下，编译器工作在“静态编译”阶段，它的优势如下：

没有严苛的时间限制：编译器工作在“静态编译”阶段。
拥有上帝视角：对控制流图（CFG）/数据流图（DFG）进行分析，可以通过多个Pass，把一种对硬件不太友好的程序表示，转译成等价的，且对硬件友好的另外一种表示。

1. 强度削弱—— 投机取巧的替换

依据：不同指令的执行延迟差异巨大（加法1周期，乘法3~5周期，访存数百周期）。
做法：在逻辑等价前提下，将“耗时长”的指令替换为“耗时短”的指令。
案例：
- y = x * 2; z = y + 5; 替换为 y = x << 1; z = y + 5;
- 乘法需3-4周期，后续加法需死等（产生气泡）；移位只需1周期，加法可通过旁路转发背靠背无缝执行。
效果：0硬件成本，性能翻2~3倍。

2. 指令调度—— 静态的见缝插针

依据：毫无瓜葛的指令，先后顺序无所谓（指令无关性）。
做法：利用上帝视角，把相互独立的指令提前，填补流水线中的Stall气泡（类似玩俄罗斯方块填缝）。
案例：两组独立的 LD (Load) -> ADD 操作。（load指令的延迟是2个时钟周期，ADD指令延迟是1个时钟周期）
- 原顺序：LD A ➡️ Stall等A ➡️ ADD A ➡️ LD B ➡️ Stall等B ➡️ ADD B（6周期）
```
; 第一组计算
LD  R1, [内存地址A]   ; 指令1：去内存拿数据 A 放到 R1
ADD R2, R1, 1       ; 指令2：把 R1 加 1 放到 R2（依赖指令1）

; 第二组计算（与第一组毫无瓜葛）
LD  R3, [内存地址B]   ; 指令3：去内存拿数据 B 放到 R3
ADD R4, R3, 1       ; 指令4：把 R3 加 1 放到 R4（依赖指令3）
```
  - 第 1 周期：执行指令 1（开始拿数据 A）
  - 第 2 周期：气泡（Stall，死等数据 A 送达）
  - 第 3 周期：执行指令 2（A 拿到了，完成加法）
  - 第 4 周期：执行指令 3（开始拿数据 B）
  - 第 5 周期：气泡（Stall，死等数据 B 送达）
  - 第 6 周期：执行指令 4（B 拿到了，完成加法）
  一共使用了6个周期，其中2个周期被浪费了，利用率为66.7%。
- 调度后：LD A ➡️ LD B（填补等A的气泡） ➡️ ADD A ➡️ ADD B（4周期，0停顿）
```
; 编译器重排后的代码：
LD  R1, [内存地址A]   ; 指令1：拿数据 A
LD  R3, [内存地址B]   ; 指令3：拿数据 B （被强行插队提前了！）
ADD R2, R1, 1       ; 指令2：算 A+1
ADD R4, R3, 1       ; 指令4：算 B+1
```
  - 第 1 周期：执行指令 1（开始拿数据 A）
  - 第 2 周期：执行指令 3（开始拿数据 B）。注意！这个周期原本是用来等 A 的气泡，现在被完美填补了！而且等这个周期结束，数据 A 刚好也送到了！
  - 第 3 周期：执行指令 2（A 到了，直接加法，无缝衔接！）
  - 第 4 周期：执行指令 4（B 到了，直接加法，无缝衔接！）
  一共使用了4个周期，其中所有周期都被充分利用，利用率为100%。
疑问：既然硬件有OoO兜底，编译器还需要调度吗？
- 需要，原因如下：
  - 硬件乱序窗口有限，编译器调度视野更宏观；
  - 编译器需均匀打散指令，以防结构性冒险；
  - 最关键：不是所有处理器都有OoO（如极简NPU），编译器是顺序执行架构的兜底者。

3. 循环展开—— 打破基本块的墙

痛点：基本块太小。程序平均4~7条指令就会遇到分支跳转（如for循环的边界判断），导致编译器找不到足够的无关指令来做调度。
做法：把循环体强行复制多份（以一定步幅展开），合并循环维护代码。（优点在于经过更多的指令后，才会遇到分支跳转）

案例：for循环给数组加常数。（load指令的延迟是2个时钟周期，ADD指令延迟是1个时钟周期）

for (i = 1000; i > 0; i--) {
    x[i] = x[i] + s;
}

未展开：处理1个元素需9周期（4周期Load气泡 + 2周期循环维护开销）。
```
Loop:
  LD   R1, 0(R2)      ; 指令1：从内存加载 x[i] 到 R1
  ADD  R1, R1, s      ; 指令2：算加法（R1 = R1 + s）
  SD   R1, 0(R2)      ; 指令3：把算好的 R1 写回内存 x[i]
  SUB  R2, R2, 8      ; 指令4：指针往后退（准备处理下一个元素）
  BNEZ R2, Loop       ; 指令5：判断是不是全处理完了，没完就跳回 Loop
```
- 第 1 周期：LD（拿数据）
- 第 2 周期：气泡 Stall（等数据到）
- 第 3 周期：气泡 Stall（等数据到）
- 第 4 周期：气泡 Stall（等数据到）
- 第 5 周期：ADD（算加法）
- 第 6 周期：气泡 Stall（等加法器把结果算稳）
- 第 7 周期：SD（写回内存）
- 第 8 周期：SUB（改指针）
- 第 9 周期：BNEZ（分支判断）
一共使用了9个周期，其中4个周期被浪费了，利用率为55.6%。

展开4份并调度：集中加载(LD) ➡️ 集中计算(ADD) ➡️ 集中写回(SD) ➡️ 1次指针维护(SUB/BNEZ)。14条指令无气泡执行，处理4个元素仅需14周期（原需36周期），性能暴涨2.57倍！

for (i = 1000; i > 0; i-=4) {
    x[i] = x[i] + s;
    x[i-1] = x[i-1] + s;
    x[i-2] = x[i-2] + s;
    x[i-3] = x[i-3] + s;
}

Loop:
  ; 【阶段 1：集中加载，填补 Load 气泡】
  LD   R1, 0(R2)      ; 拿 x[i]
  LD   R3, -8(R2)     ; 拿 x[i-1] （直接塞进原本等 R1 的气泡里！）
  LD   R5, -16(R2)    ; 拿 x[i-2] （直接塞进原本等 R1|R3 的气泡里！）
  LD   R7, -24(R2)    ; 拿 x[i-3] （直接塞进原本等 R1|R3|R5 的气泡里！）
  
  ; 【阶段 2：集中计算，此时前面的数据会陆续准备好】
  ADD  R1, R1, s      ; 算 x[i] + s   （ R1 准备好了）
  ADD  R3, R3, s      ; 算 x[i-1] + s （ R3 准备好了）
  ADD  R5, R5, s      ; 算 x[i-2] + s （ R5 准备好了）
  ADD  R7, R7, s      ; 算 x[i-3] + s （ R7 准备好了）
  
  ; 【阶段 3：集中写回】
  SD   R1, 0(R2)      
  SD   R3, -8(R2)     
  SD   R5, -16(R2)    
  SD   R7, -24(R2)    
  
  ; 【阶段 4：只做一次循环维护】
  SUB  R2, R2, 32     ; 指针一次性退 4 个元素的位置
  BNEZ R2, Loop       ; 判断

一共使用了14个周期，但是每个周期都是被充分利用的。原本的方法一共需要 $4 \times 9 =36$ 个周期，但是目前的方法只需要14个周期，并且也有相同的产出。

循环展开的两大绝对优势：
1. 摊薄管理成本：减少了分支判断和指针修改的次数（消除了控制冒险，硬件分支预测狂喜）。
2. 暴增指令池：将原本锁在墙内的几条指令平铺开来，给编译器提供了极其广阔的调度空间，完美掩盖硬件延迟。

关键概念钩子：带条挖掘

循环展开时，如果循环次数不能被展开步幅整除怎么办？

解法：工业级编译器采用带条挖掘技术。主体循环按固定步幅打包处理，末尾单独生成一段标量代码（“尾巴”逻辑）去扫尾处理余下的元素。
重要意义：不仅是循环展开的基础，更是后续**数据级并行（DLP/SIMD向量化）**的绝对核心（如何将任意长度数组切块喂入固定宽度的向量寄存器）。

Arch and Compiler