通过提前计算条件来避免管道停滞

无序执行绝对是一回事（不仅是编译器，甚至处理器芯片本身也可以对指令进行重新排序），但它对数据依赖引起的管道停滞比对错误预测引起的流水线停滞更有帮助。

控制流方案的好处在某种程度上受到以下事实的限制：在大多数体系结构上，条件分支指令仅根据标志寄存器做出决策，而不是基于通用寄存器。除非中间的“工作”非常不寻常，否则很难提前很久设置标志寄存器，因为大多数指令都会更改标志寄存器（在大多数架构上）。

也许确定以下组合

TST (reg)
J(condition)

可以设计为在提前设置足够远时最大限度地减少失速。当然，这需要处理器的很大程度的帮助，而不仅仅是编译器。处理器设计人员可能会针对更普遍的情况进行优化，即提前（无序）执行为分支设置标志的指令，结果标志通过管道转发，提前结束停顿。(reg)

是的，尽早计算分支条件可能是有益的，这样任何误报都可以尽早解决，管道的前端部分可以尽早开始重新填充。在最好的情况下，如果已经有足够的工作来完全隐藏前端泡沫，那么错误预测可能是免费的。

不幸的是，在无序 CPU 上，早期有一个微妙的定义，因此让分支尽早解析并不像在源代码中移动行那么简单 - 您可能需要更改条件的计算方式。

什么不起作用

遗憾的是，前面没有引用源文件中条件/分支的位置，也没有引用与比较或分支对应的汇编指令的位置。因此，从根本上讲，它大多是⁷ 不像您的示例那样工作。

即使源级定位很重要，它也可能在您的示例中不起作用，因为：

您已经将条件的评估上移并将其分配给 ，但可能错误预测的不是测试（运算符），而是后续的条件分支：毕竟，这是一个分支错误预测。在您的示例中，分支在两个位置都位于同一位置：其形式只是从 更改为 。bool<if (a > b)if (aGreaterThanB)

除此之外，转换代码的方式不太可能欺骗大多数编译器。优化编译器不会按照编写代码的顺序逐行发出代码，而是根据源代码级依赖项按他们认为合适的方式安排内容。提前拉起条件可能会被忽略，因为编译器希望将检查放在它自然会去的地方：大约在带有标志寄存器的架构的分支之前。

例如，请考虑简单函数的以下两个实现，它们遵循您建议的模式。第二个函数将条件向上移动到函数的顶部。

int test1(int a, int b) {
    int result = a * b;
    result *= result;
    if (a > b) {
        return result + a;
    }
    return result + b * 3;
}

int test2(int a, int b) {
    bool aGreaterThanB = a > b;
    int result = a * b;
    result *= result;
    if (aGreaterThanB) {
        return result + a;
    }
    return result + b * 3;
}

我检查了 gcc、clang² 和 MSVC，并且都以相同的方式编译了这两个函数（编译器之间的输出不同，但对于每个编译器，这两个函数的输出是相同的）。例如，编译结果如下：test2gcc

test2(int, int):
  mov eax, edi
  imul eax, esi
  imul eax, eax
  cmp edi, esi
  jg .L4
  lea edi, [rsi+rsi*2]
.L4:
  add eax, edi
  ret

该指令与条件相对应，gcc 已将其移回所有“工作”之后，并将其放在条件分支旁边。cmpa > bjg

什么有效

因此，如果我们知道在源代码中对操作顺序的简单操作是行不通的，那么什么行得通呢？事实证明，在数据流图中将分支条件“向上”移动的任何操作都可以通过更早地解决错误预测来提高性能。我不打算深入探讨现代 CPU 如何依赖于数据流，但您可以在此处找到简要概述，并在最后提供进一步阅读的指针。

遍历链表

下面是一个涉及链接列表遍历的真实示例。

考虑将所有值求和的任务，一个以 null 结尾的链表，该链表也将其长度¹ 存储为列表头结构的成员。链表实现为一个对象和零个或多个列表节点（具有单个有效负载），定义如下：list_headint value

struct list_node {
    int value;
    list_node* next;
};

struct list_head {
    int size;
    list_node *first;
};

规范搜索循环将使用最后一个节点中的哨兵来确定是否已到达列表的末尾，如下所示：node->next == nullptr

long sum_sentinel(list_head list) {
    int sum = 0;
    for (list_node* cur = list.first; cur; cur = cur->next) {
        sum += cur->value;
    }
    return sum;
}

这和你得到的一样简单。

但是，这会将结束求和的分支（第一个分支）置于节点到节点指针跟踪的末尾，这是数据流图中最长的依赖项。如果此分支预测错误，则错误预测的解决将“延迟”发生，并且前端气泡将直接添加到运行时。cur == null

另一方面，您可以通过显式计算节点来进行求和，如下所示：

long sum_counter(list_head list) {
    int sum = 0;
    list_node* cur = list.first;
    for (int i = 0; i < list.size; cur = cur->next, i++) {
        sum += cur->value;
    }
    return sum;
}

与哨兵解决方案相比，我们似乎增加了额外的工作：我们现在需要初始化、跟踪和递减计数⁴。然而，关键是这个递减依赖链非常短，因此它将“领先”指针追逐工作，并且错误预测将提前发生，而仍然有有效的剩余指针追逐工作要做，可能会在运行时有很大的改进。

让我们实际尝试一下。首先，我们检查两个解决方案的程序集，以便我们可以验证是否发生任何意外：

<sum_sentinel(list_head)>:
test   rsi,rsi
je     1fe <sum_sentinel(list_head)+0x1e>
xor    eax,eax
loop:
add    eax,DWORD PTR [rsi]
mov    rsi,QWORD PTR [rsi+0x8]
test   rsi,rsi
jne    loop
cdqe   
ret    


<sum_counter(list_head)>:
test   edi,edi
jle    1d0 <sum_counter(list_head)+0x20>
xor    edx,edx
xor    eax,eax
loop:
add    edx,0x1
add    eax,DWORD PTR [rsi]
mov    rsi,QWORD PTR [rsi+0x8]
cmp    edi,edx
jne    loop:
cdqe   
ret    

正如预期的那样，哨兵方法稍微简单一些：在设置过程中少一条指令，在循环⁵ 中少一条指令，但总的来说，关键指针追逐和加法步骤是相同的，我们预计这个循环将由连续节点指针的延迟主导。

事实上，当预测影响可以忽略不计时，在对短列表或长列表求和时，循环的性能几乎相同。对于长列表，分支预测的影响自动很小，因为到达列表末尾时的单个错误预测会在许多节点上摊销，并且对于 L1 中包含的列表，运行时几乎正好达到每个节点 4 个周期，这是我们对英特尔最佳情况下 4 个周期加载到使用延迟的预期。

对于短列表，如果列表的模式是可预测的，则分支错误预测是可以忽略的：要么始终相同，要么在某个中等周期内循环（如果预测良好，可以是 1000 个或更多！在这种情况下，当对许多短列表求和时，每个节点的时间可以少于 4 个周期，因为多个列表可以同时进行（例如，如果汇总列表数组）。在任何情况下，这两种实现的性能几乎相同。例如，当列表始终有 5 个节点时，对一个列表求和的时间约为 12 个周期，采用任一实现：

** Running benchmark group Tests written in C++ **
                     Benchmark   Cycles   BR_MIS
       Linked-list w/ Sentinel    12.19     0.00
          Linked-list w/ count    12.40     0.00

让我们将分支预测添加到组合中，方法是更改列表生成代码以创建平均长度为 5 但实际长度均匀分布在 中的列表。求和码保持不变：只是输入不同。随机列表长度的结果：[0, 10]

** Running benchmark group Tests written in C++ **
                     Benchmark   Cycles   BR_MIS
       Linked-list w/ Sentinel    43.87     0.88
          Linked-list w/ count    27.48     0.89

该列显示，正如预期的那样，我们每个列表⁶ 都得到了近一个分支错误预测，因为循环出口是不可预测的。BR_MIS

但是，哨兵算法现在需要 ~44 个周期，而计数算法需要 ~27.5 个周期。计数算法快了大约 16.5 个周期。您可以使用列表长度和其他因素，并更改绝对时序，但增量几乎总是在 16-17 个周期左右，这与最近英特尔的分支错误预测惩罚大致相同，这并非巧合！通过尽早解决分支条件，我们避免了前端气泡，在这种气泡中，什么都不会发生。

提前计算迭代计数

另一个例子是计算浮点值的循环，比如泰勒级数近似，其中终止条件取决于计算值的某个函数。这与上述效果相同：终止条件取决于慢循环携带的依赖关系，因此它的解析速度与值本身的计算一样慢。如果出口不可预测，您将在出口时遇到停滞。

如果可以更改它以预先计算迭代计数，则可以使用解耦的整数计数器作为终止条件，从而避免冒泡。即使前期计算增加了一些时间，它仍然可以提供整体加速（无论如何，计算可以与循环的第一次迭代并行运行，因此通过查看其延迟，它的成本可能要低得多）。

---

¹ MIPS是一个有趣的例外，它没有标志寄存器 - 测试结果直接存储在通用寄存器中。

² Clang 以无分支的方式编译了这个和许多其他变体，但它仍然很有趣，因为你仍然具有相同的测试指令结构和条件移动（取代分支）。

³ 像 C++11 .std::list

⁴ 事实证明，在 x86 上，两种方法之间的每个节点工作实际上非常相似，因为隐式设置零标志的方式，因此我们不需要额外的指令，而指针追逐中使用的则不需要，因此计数器方法具有额外的功能，而哨兵方法具有额外的测试， 让它大约洗一洗。dectestmovdec

⁵ 虽然这部分只是因为 gcc 没有设法将递增的 for 循环转换为递减的循环以利用设置零标志的优势，但避免了 .也许较新的 gcc 版本做得更好。另见脚注4。deccmp

⁶ 我想这更接近 0.9 而不是 1.0，因为也许分支预测器仍然会得到正确的长度 = 10 大小写，因为一旦你循环了 9 次，下一次迭代将始终退出。合成性较差/精确的分布不会表现出来。

⁷ 我之所以这么说，主要是因为在某些情况下，您可以通过这种源代码或程序集级别的重新排序来节省一两个周期，因为这些事情可能会对无序处理器中的执行顺序产生轻微影响，执行顺序也受程序集顺序的影响，但仅限于数据流图的约束范围内。另请参阅此评论。

分支错误预测的主要问题不在于它在刷新年轻操作时产生的几个周期（相对较快），而是如果存在数据依赖关系，它可能会在管道上很晚发生，分支条件必须首先解决。

对于基于先前计算的分支，依赖项的工作方式与其他操作相同。此外，分支很早就沿着管道进行预测，以便机器可以继续获取和分配进一步的操作。如果预测不正确（这与通常表现出更可预测的模式的循环控件不同，则仅当依赖关系得到解决并且预测被证明是错误的时，才会发生刷新。这种情况发生得越晚，处罚就越大。

由于无序执行会在解决依赖关系后立即调度操作（假设没有端口压力），因此提前移动操作可能无济于事，因为它不会改变依赖关系链，也不会对调度时间产生太大影响。唯一的潜在好处是，如果你把它移得足够远，这样 OOO 窗口就可以更早地看到它，但现代 CPU 通常会提前运行数百条指令，并且在不破坏程序的情况下将指令提升到那么远是很困难的。但是，如果您正在运行一些循环，那么如果可能的话，计算未来迭代的条件可能很简单。

这些都不会改变完全正交的预测过程，但是一旦分支到达机器的OOO部分，它将立即得到解决，如果需要，它会被清除，并产生最小的惩罚。