# H.4 暴露并行性的硬件支持：谓词指令
<!-- source: p1152 -->

如果编译时能够较准确地预测分支行为，循环展开、软件流水线和踪迹调度等技术就能增加可用并行性。如果分支行为不明确，仅靠编译器可能无法发现很多 ILP，控制依赖会严重限制可开发的并行性。为克服这些问题，体系结构设计者可以扩展指令集，加入条件指令或谓词指令。它们能够消除分支，将控制依赖转化为数据依赖，从而有望改善性能。这既适用于第 3 章侧重硬件的方法，也适用于本附录侧重软件的方法，因为两类方法都能借助谓词化消除分支。

条件指令的概念很简单：指令引用一个条件，执行时检查该条件。条件为真就正常执行；条件为假，程序继续执行，效果如同该指令是一条空操作。许多较新的体系结构包含某种条件指令。最常见的是**条件传送**（conditional move）：仅当条件为真时，才把值从一个寄存器传送到另一个寄存器。在简单的代码序列中，这类指令能够完全消除分支。

**例题**　考虑以下代码：

~~~c
if (A==0) {S=T;}
~~~

假设 R1、R2、R3 分别保存 A、S、T，给出使用分支和使用条件传送的两种实现。

**解答**　直接采用分支的实现如下。注意，这里假定采用普通分支，而不是延迟分支。

~~~asm
BNEZ R1,L
ADDU R2,R3,R0
L:
~~~

若条件传送在第三个操作数等于零时才执行传送，则一条指令就够了：

~~~asm
CMOVZ R2,R3,R1
~~~

<!-- source: p1153 -->

条件指令将原先分支代码中的控制依赖转化为数据依赖。向量计算机也使用这种变换，称为 **if 转换**（if conversion）。在流水线处理器中，依赖必须解决的位置因此从流水线前部、原先处理分支的位置，后移到流水线末端、写寄存器的位置。

条件传送的一个明显用途是实现绝对值函数 `A = abs(B)`，即 `if (B<0) {A=-B;} else {A=B;}`。该语句可以用两次条件传送实现，也可用一次无条件传送 `A=B` 加一次条件传送 `A=-B` 实现。

上述例子和绝对值函数的编译，都通过条件传送将控制依赖转化为数据依赖，消除分支，并可能改善流水线行为。发射率不断提高，设计者必须在两种选择之间取舍：每周期执行多个分支，或设法消除分支来避免这一要求。每周期处理多个分支十分复杂，因为其中一个分支必然控制依赖于另一个分支。准确预测两个分支的结果、更新预测表、执行正确序列，都很困难；因此，迄今大多数设计者都避免采用每周期执行多个分支的处理器。条件传送和谓词指令能够减轻分支压力。此外，条件传送常常可以消除难以预测的分支，进一步增大潜在收益。

条件传送是条件指令或谓词指令最简单的形式。它适合短序列，却有局限：如果分支保护的是大段代码，为消除分支可能必须引入许多条件传送，效率并不高。

为弥补这一不足，一些体系结构支持**完全谓词化**（full predication），由谓词控制所有指令的执行。谓词为假时，指令成为空操作。这样可以直接转换依赖于分支的大段代码。例如，循环中的 if-then-else 可以全部转为谓词执行：条件为真时只执行 then 部分，为假时只执行 else 部分。谓词化对全局代码调度尤其有价值，因为它可以消除使指令调度显著复杂化的非循环分支。

谓词指令也能让时间敏感的指令提前推测执行，即使将它直接移到保护分支之前可能引发异常。条件传送也能实现这一目的，但代价更高。

<!-- source: p1154 -->

**例题**　下面是一段双发射超标量处理器的代码。每周期可以发射一条存储器访问和一条 ALU 操作，或者单独发射一条分支。

| 第一个指令槽 | 第二个指令槽 |
| --- | --- |
| `LW R1,40(R2)` | `ADD R3,R4,R5` |
| | `ADD R6,R3,R7` |
| `BEQZ R10,L` | |
| `LW R8,0(R10)` | |
| `LW R9,0(R8)` | |

第二周期的存储器操作槽被浪费了。如果分支不跳转，还会出现数据依赖停顿，因为分支之后第二条 LW 依赖前一条加载。请使用谓词化的 LW 改善这段代码。

**解答**　将谓词化的字加载称为 LWC，假设第三个操作数非零时才执行加载。紧跟分支的 LW 可以改为 LWC，并提前到第二次发射：

| 第一个指令槽 | 第二个指令槽 |
| --- | --- |
| `LW R1,40(R2)` | `ADD R3,R4,R5` |
| `LWC R8,0(R10),R10` | `ADD R6,R3,R7` |
| `BEQZ R10,L` | |
| `LW R9,0(R8)` | |

这样既省去一次指令发射位置，又减少最后一条指令的流水线停顿，执行时间可缩短数个周期。当然，如果编译器对分支的预测错误，这条谓词指令就不产生效果，也不会改善运行时间；因此，这种变换具有推测性。

如果分支后面的序列很短，就可以将整段代码转为谓词执行，并删除分支。

将整个代码段转换为谓词执行，或提前移动一条推测指令并使之谓词化，都会消除控制依赖。正确的代码生成与谓词指令的条件执行，共同保证原先由分支约束的数据流不变。为了保持异常行为，谓词为假时，谓词指令不能产生异常。这一点非常关键：在前例中，若 R10 为零，无条件执行 `LW R8,0(R10)` 很可能触发保护异常，而这种异常本不应发生。

<!-- source: p1155 -->

当然，如果条件满足，即 R10 非零，LW 仍可能触发合法、可恢复的异常，例如缺页；当硬件知道控制条件为真时，就必须处理这种异常。

实现谓词指令的主要难点是决定何时撤销指令。可以在指令发射时撤销，也可以在流水线后部、提交结果或引发异常之前撤销。两种选择各有缺点。如果很早就撤销，控制条件也必须很早确定，否则会因数据冒险而停顿。那些依赖数据、较难预测的分支条件，恰恰是谓词化的候选，因此早期撤销可能增加流水线停顿。正因为这种潜在停顿，现有支持谓词执行或条件传送的设计都不在早期撤销，而是在流水线后部撤销。这意味着被撤销的指令仍会消耗功能单元资源，并可能损害性能。前递等其他流水线实现技术也会与谓词指令相互作用，进一步增加复杂性。

谓词指令或条件指令，对于实现简短的控制流分支、消除部分难预测分支、降低全局代码调度开销，都非常有用。然而，其用途受到几个因素限制：

- **被撤销的谓词指令仍消耗处理器资源。** 条件为假的指令至少占用取指资源，在大多数处理器上还占用功能单元执行时间。因此，把指令移过分支并改为条件执行，如果该指令原本不会执行，就会拖慢程序。同理，将依赖控制的代码段谓词化并消除分支，如果该段原本不会执行，也可能使处理器变慢。一个重要例外是：该指令占用的周期原本就会空闲，前面的超标量例子正是如此。跨分支移动指令、或将代码转换为谓词执行，本质上都是对分支结果进行推测。条件指令让这件事更容易，却无法消除猜错时占用的执行时间。在用一条条件传送替换“分支加传送”的简单场景中，条件传送或谓词化几乎总是更好；当较长序列被改为条件执行时，收益就更有限。
- **谓词能够提早求值时最有用。** 如果确定条件所需的数据依赖，使条件求值和谓词指令无法分开调度，条件指令就可能因为数据冒险而停顿。

<!-- source: p1156 -->

  分支预测与推测执行可以避免这种停顿，至少在预测准确时如此。

- **控制流比简单的二选一序列更复杂时，条件指令的使用可能受限。** 例如，把指令移过多个分支，需要让它同时受这些分支条件控制；这要求指定两个条件，或者添加指令来计算控制谓词。缺乏这种能力时，if 转换的开销更大，优势也更小。
- **条件指令可能比无条件指令更慢。** 代价可能表现为指令所需周期数增加，或整个处理器的时钟频率降低。如果条件指令更昂贵，就必须审慎使用。

因此，许多体系结构包含少数简单条件指令，最常见的是条件传送；只有少数体系结构为大部分指令提供条件版本。MIPS、Alpha、PowerPC、SPARC，以及以 Pentium 处理器定义的 Intel x86，都支持条件传送。IA-64 则支持所有指令的完全谓词化，H.6 节将介绍。