3.2 显露 ILP 的基本编译器技术

本节考察如何利用简单的编译器技术，增强处理器开发 ILP 的能力。这些技术对于采用静态发射或静态调度的处理器至关重要。

掌握这些编译器技术后，我们将在后文研究采用静态发射的处理器的设计与性能。附录 H 将研究更复杂的编译器方案及配套硬件，以便处理器开发更多 ILP。

基本流水线调度与循环展开

要让流水线保持满载，必须找出可以在流水线中重叠执行的独立指令序列，开发指令之间的并行性。为避免流水线停顿，一条有依赖的指令与产生其源数据的指令之间，必须间隔相当于源指令流水线延迟的时钟周期数。编译器能否进行这种调度，既取决于程序中可用的 ILP，也取决于流水线中各功能单元的延迟。除非明确另作说明，本章均采用图 3.2 的浮点单元延迟。我们假设使用标准的五级整数流水线，因此分支有 1 个时钟周期的延迟。我们还假设各功能单元完全流水线化，或者复制了与流水线深度相同的份数，使任意类型的操作都能在每个时钟周期发射，不存在结构冒险。

图 3.2 本章采用的浮点操作延迟。最后一列是为避免停顿，两条指令之间需要插入的时钟周期数。这些数值与浮点单元的平均延迟相近。浮点加载到存储的延迟为 0，因为加载结果可以经旁路直接提供给存储，无需使存储停顿。我们继续假设整数加载的延迟为 1，整数 ALU 操作的延迟为 0，后者也包括从 ALU 操作到分支的情况。

本节考察编译器如何通过变换循环，增加可用的 ILP。这个例子既展示一种重要技术，也引出附录 H 中更强大的程序变换。我们使用下面这段代码，把一个标量加到一个双精度（64 位）浮点向量的所有元素上：

for (i=999; i>=0; i=i-1)
    x[i] = x[i] + s;

每次迭代的循环体彼此独立，因此这个循环可以并行执行。附录 H 将形式化地说明这一概念，并介绍如何在编译时判断循环迭代是否独立。这里先分析这个循环的性能，看看对于具有给定延迟的 RISC-V 流水线，怎样利用并行性提高性能。

第一步是将上述代码转换为 RISC-V 汇编语言。在下面的代码中，寄存器 x1 初始化为数组中地址最高的元素的地址，f2 保存标量值 $s$。寄存器 x2 的初值满足：x2+8 是最后一个待处理数组元素的地址。

直接转换得到、尚未针对流水线调度的 RISC-V 代码如下：

Loop: fld    f0,0(x1)     // f0 = 数组元素
      fadd.d f4,f0,f2     // 加上 f2 中的标量
      fsd    f4,0(x1)     // 存储结果
      addi   x1,x1,-8     // 指针减去 8 字节（64 位数）
      bne    x1,x2,Loop   // x1 ≠ x2 时跳转

先看看把该循环调度到延迟如图 3.2 所示的简单 RISC-V 流水线上时，运行效果如何。

例题 展示该循环在 RISC-V 流水线上未调度与调度后的执行情况，包括所有停顿或空闲时钟周期。调度时应考虑浮点操作的延迟。

解答 未进行任何调度时，循环按下表执行，每个数组元素需要 9 个周期。¹

经过调度，可以只保留两次停顿，将时间缩短为 7 个周期：

Loop: fld    f0,0(x1)
      addi   x1,x1,-8
      fadd.d f4,f0,f2
      // 停顿
      // 停顿
      fsd    f4,8(x1)
      bne    x1,x2,Loop

fadd.d 之后的停顿，是为了等待 fsd 使用它的结果；调整 addi 的位置，则避免了 fld 之后的停顿。

在上例中，每 7 个时钟周期完成一次迭代，并写回一个数组元素，但真正操作数组元素的工作只占其中 3 个周期，即加载、加法与存储。其余 4 个周期是循环开销——addi 和 bne——以及两次停顿。要消除这 4 个周期，就需要相对于开销指令，增加实际操作的数量。

相对于分支与开销指令，增加实际指令数量的一种简单办法是循环展开。展开只是将循环体复制多次，并调整循环终止代码。

循环展开也能改善调度。它降低分支出现的频率，使来自多次迭代的指令可以一起调度。这样，通过交错安排展开后的各次迭代指令，就能消除数据使用停顿。如果展开时仅仅复制指令，重复使用同一组寄存器可能妨碍有效调度。因此，我们希望每次迭代使用不同的寄存器，这会增加所需的寄存器数量。

例题 将该循环展开为包含 4 份循环体的形式。假设 x1−x2，即数组大小，初始为 32 的倍数，意味着循环迭代次数为 4 的倍数。消除明显冗余的计算，不重复使用任何寄存器。

解答 合并 addi 指令，并删去展开时复制出的多余 bne 后，结果如下。注意，现在 x2 的初值应满足：x2+32 是最后 4 个元素的起始地址。

Loop: fld    f0,0(x1)      // 第 1 个元素的代码
      fadd.d f4,f0,f2
      fsd    f4,0(x1)      // 删去 addi 和 bne
      fld    f6,-8(x1)     // 第 2 个元素的代码
      fadd.d f8,f6,f2
      fsd    f8,-8(x1)     // 删去 addi 和 bne
      fld    f0,-16(x1)    // 第 3 个元素的代码
      fadd.d f12,f0,f2
      fsd    f12,-16(x1)   // 删去 addi 和 bne
      fld    f14,-24(x1)   // 第 4 个元素的代码
      fadd.d f16,f14,f2
      fsd    f16,-24(x1)
      addi   x1,x1,-32
      bne    x1,x2,Loop

译注：上面的第 3 份循环体在原页中确实使用 f0，与题目“不重复使用寄存器”的要求不符；下一例调度后的对应位置使用 f10。

我们消除了 3 条分支和 3 次对 x1 的递减。加载与存储指令中的地址作了补偿，因而可以合并修改 x1 的 addi 指令。这种优化看似简单，实际上需要符号代换与化简。符号代换和化简会重组表达式，使常数可以合并，例如把 $((i+1)+1)$ 改写为 $(i+(1+1))$，再化简为 $(i+2)$。附录 H 将介绍更一般的此类优化，用来消除存在依赖的计算。循环展开通常在编译过程的早期进行，使冗余计算显露出来，再由优化器消除。

若不进行调度，展开后的循环中，每条浮点加载或运算后面都紧接着一条依赖它的操作，因此都会引起停顿。这个展开后的循环需要 26 个时钟周期：每条 fld 停顿 1 个周期，每条 fadd.d 停顿 2 个周期，再加上 14 个指令发射周期；平均每个元素 6.5 个时钟周期。但经过调度，性能还能显著提高。

真实程序中，通常无法事先知道循环次数的上界。假设它为 $n$，我们希望展开循环，生成 $k$ 份循环体。这时不生成单个展开循环，而是生成两个连续的循环。第一个执行 $n\bmod k$ 次，循环体与原循环相同。第二个以展开后的循环体为主体，外层循环迭代 $n/k$ 次。（第 4 章会看到，这与向量处理器编译器中称为 strip mining 的技术相似。）当 $n$ 很大时，大部分执行时间会花在展开后的循环体中。

上例通过展开消除开销指令，提高了循环性能，但也明显增大了代码。若针对前述流水线进行调度，展开后的循环性能如何？

例题 按图 3.2 的流水线延迟，对上例的展开循环进行调度，给出结果。

解答

Loop: fld    f0,0(x1)
      fld    f6,-8(x1)
      fld    f10,-16(x1)
      fld    f14,-24(x1)
      fadd.d f4,f0,f2
      fadd.d f8,f6,f2
      fadd.d f12,f10,f2
      fadd.d f16,f14,f2
      fsd    f4,0(x1)
      fsd    f8,-8(x1)
      fsd    f12,16(x1)
      fsd    f16,8(x1)
      addi   x1,x1,-32
      bne    x1,x2,Loop

译注：原页中最后两条存储的偏移确为正的 16、8，而 addi x1,x1,-32 位于它们之后。按所示顺序，这两个地址与对应加载的 -16、-24 不一致，不能保持原循环的数据写回位置。若将指针递减移到这两条存储之前，或在现有位置使用 -16、-24，才能恢复对应地址；此处不替换原代码。

展开循环的总执行时间已降至 14 个时钟周期，即每个元素 3.5 个周期；相比之下，完全未展开、未调度时，每个元素为 8 个周期，已展开但未调度时则为 6.5 个周期。¹

调度对展开循环带来的收益，比对原始循环更大。原因是循环展开显露出更多独立指令，可以通过调度最大限度地减少停顿；上述代码已经没有停顿。以这种方式调度循环，必须先认识到加载与存储彼此独立，可以交换顺序。

循环展开与调度小结

本章与附录 H 将介绍多种硬件与软件技术，利用 ILP 充分发挥处理器功能单元的潜力。多数技术的关键，是知道何时可以改变指令顺序，以及如何改变。在上面的例子中，我们进行了多次这样的改动；在人看来，这些改动显然是允许的。但实际系统必须由编译器或硬件，以系统化的方式完成这一过程。要得到最终的展开代码，需要作出以下判断与变换：

• 确认除循环维护代码之外，各次循环迭代彼此独立，从而判断循环展开能够带来收益。
• 使用不同寄存器，避免不同计算使用同一寄存器而产生不必要的约束，例如名依赖。
• 消除多余的测试与分支指令，调整循环终止和迭代代码。
• 观察到不同迭代中的加载和存储相互独立，从而确定展开后的加载与存储可以交换顺序。这种变换需要分析内存地址，确认它们没有指向同一地址。
• 调度代码，并保留一切为获得与原代码相同结果所必需的依赖。

所有这些变换共同的基础，是理解一条指令如何依赖另一条指令，以及在这些依赖之下，可以怎样修改或重新排列指令。

循环展开的收益受三种因素限制：（1）每进一步展开一次，能够摊薄的开销越来越少；（2）代码大小限制；（3）寄存器压力。先考虑循环开销。将循环展开 4 次后，指令之间已有足够的并行性，可以调度得完全没有停顿。实际上，14 个时钟周期中只有 2 个属于循环开销：维护下标值的 addi，以及结束循环的 bne。如果展开 8 次，开销就从每个元素 1/2 个周期降至 1/4 个周期。

第二项限制是展开导致代码增大。对于较大的循环，这可能成为问题，尤其是因此提高指令缓存未命中率时。

另一个常常比代码大小更重要的因素，是激进展开和调度可能造成寄存器不足。这种在大段代码中进行指令调度所产生的次生影响，称为寄存器压力。为了增加 ILP 而调度代码，会使活跃值的数量增加，这正是寄存器压力的来源。经过激进的指令调度后，可能无法为所有活跃值分配寄存器。变换后的代码在理论上更快，却可能因为寄存器短缺而失去部分乃至全部优势。不进行展开时，分支会充分限制激进调度，因此寄存器压力很少成为问题。但将展开与激进调度结合起来，就可能出现这一问题。对于多发射处理器，这一点尤其棘手，因为它们需要显露出更多可以重叠执行的独立指令序列。总体而言，复杂高层变换的潜在收益在生成详细代码之前很难测量，而这类变换的使用已使现代编译器的复杂度显著增加。

循环展开是增大可有效调度的直线代码片段的一种简单而实用的方法。它适用于多种处理器，从我们目前讨论的简单流水线，到本章后面将研究的多发射超标量处理器与 VLIW 处理器。