分支预测失误是否会使整个流水线清空，即使是非常短的if语句体？

Question

我所阅读的所有内容都表明，分支预测错误总是导致整个流水线被清空，这意味着大量的浪费周期。我从未听说过任何关于短if条件的例外。

这在某些情况下似乎非常浪费。例如，假设你有一个单独的if语句，其非常简单的主体被编译成1个CPU指令。if子句会被编译为向前条件跳转一个指令。如果CPU预测分支不被采取，则它将开始执行if主体指令，并可以立即开始执行以下指令。现在，一旦对if条件的评估达到流水线的末尾，可能需要12个周期，CPU现在知道它的预测是正确还是错误的。如果它预测错误，并且分支实际上被采取了，那么CPU只需要丢弃流水线中的1个指令（在if主体中）。但是，如果刷新整个流水线，那么对以下指令进行的所有工作也都被浪费了，而且没有理由要重复。这是在深度流水线结构上浪费了很多周期。

那么现代CPU是否有机制只丢弃短if主体内的几个指令？还是真的清空整个流水线？如果是后者，那么使用条件移动指令将获得更好的性能。另外，是否有人知道现代编译器在将短if语句转换为cmov指令方面表现良好？

- Norg74

---

一种实现这个的技术被称为动态预测（通常只用于吊床分支）。对于单指令前向分支，这实际上是在POWER7中实现的。（“愿望分支”被提出来为可能使用动态预测的分支提供硬件提示）。权衡是复杂的（特别是对于乱序处理器）。特殊处理不是免费的，因此，如果分支预测准确率很高，则使用预测而不是预测是有意义的。（以后可能会写一个答案。） - user2467198

Answer 1

大多数通用处理器在分支预测错误时会刷新流水线。条件分支的负面性能影响已经促进了急切执行（其中两个路径都被执行，然后选择正确的路径）和动态预测（其中分支阴影中的指令是有条件的）的提议，以及对分支预测（以及其他技术）的广泛研究。（Mark Smotherman关于急切执行的页面提供了一些详细信息和参考资料。我还想添加Hyesoon Kim等人的“Wish Branches：结合条件分支和预测进行自适应预测执行”，2005年，作为一篇重要论文。）

IBM的POWER7似乎是第一个实现比预取替代路径更复杂的主流处理器（即，急切获取），而且它只处理单个指令情况。（POWER7使用分支预测置信度估计来选择是否预测或使用预测。）

急切执行存在明显的资源消耗问题。即使基于分支预测置信度、推测深度和资源可用性（前端可用信息）进行选择性急切，沿着单一路径更深层次的推测往往更加有效。发现多条路径的连接点并避免过多的冗余计算也会增加复杂性。（理想情况下，控制独立操作只会执行一次，并且连接和数据流会被优化，但这样的优化会增加复杂性。）

对于一个深度流水线的顺序处理器而言，预测短向前分支不被采纳，并仅在实际采取该分支时将流水线中向后清空到被该分支指向的指令可能看起来是有吸引力的。如果每次只允许一个这样的分支进入流水线（其他分支使用预测），则为每个指令添加一个位可以控制其是否转换为nop或执行。（如果仅处理跨越单个指令的情况，则允许流水线中存在多个分支可能并不特别复杂。）

这类似于在采取分支时废除的分支延迟槽。MIPS具有“分支可能”指令，如果未采取则作废，这些指令在修订2.62中被标记为过时。虽然其中一些理由可能是为了将实现与接口分离以及希望恢复指令编码空间，但这个决定也暗示着该概念存在一些问题。

如果对所有短向前分支都这样做，当分支正确预测为已执行时，它将会丢弃指令。(请注意，如果已执行的分支总是经历提取重定向的延迟，这在深度流水线处理器中更有可能出现，那么这种惩罚可能会减少，此时按照没有分支提取与正确预测的执行分支具有相同的性能。然而，可以认为处理器特殊处理这样的短执行分支，以最小化此类提取气泡。)

作为一个例子，考虑一个标量流水线（每个周期的非分支指令等于1.0），其中分支决议在第八阶段结束，对于正确预测的转移分支没有取指重定向惩罚，处理单条指令的跨越分支。假设这样的短前向分支（占指令的2%，被执行30%）的分支预测器准确率为75%（不受方向影响），其他分支（占指令的18%）的准确率为93%。如果将短分支错误地预测为“已执行”，可以节省8个周期（这样的分支有17.5%会被错误地预测为已执行，占指令的0.35%），如果将其错误地预测为“未执行”，可以节省7个周期（这样的分支有7.2%会被错误地预测为未执行，占指令的0.144%），如果正确地预测为“已执行”，则会损失1个周期（22.5%，占指令的0.45%）。总体而言，每条指令可节省0.03358个周期。如果没有这种优化，每条指令需要1.2758个周期。

尽管上述数字仅为示例，但它们可能与现实并不远，除了非分支指令的1.0 IPC。提供小型循环缓存将减少错误预测的惩罚（并在短循环中节省功率），因为指令缓存访问可能是八个周期中的三个。添加缓存未命中的影响将进一步降低此分支优化的百分比改善。避免针对预测“强烈采取”的短分支的开销可能是值得的。

为了设计，倾向于使用较窄和较浅的流水线，并偏爱简单性（以降低设计、功率和面积成本）。由于指令集可能支持许多短分支情况下的无分支代码，因此优化这个方面的激励进一步降低。

对于乱序实现，可能会对潜在分支的指令进行预测，因为处理器希望能够执行后续的非相关指令。预测引入了额外的数据依赖性，必须检查调度。指令调度器通常仅提供每个指令两个比较器，并拆分条件移动（一个只有三个数据流操作数的简单指令：旧值、备用值和条件；一个受谓词控制的寄存器-寄存器加法将有四个操作数。（有其他解决此问题的方法，但本答案已经很长了。）

一种乱序实现也不会在分支条件不可用时停滞。这是控制依赖和数据依赖之间的权衡。通过准确的分支预测，控制依赖非常廉价，但数据依赖可能会阻碍前进等待数据操作数。(当然，对于布尔数据依赖，值预测变得更具吸引力。在某些情况下，使用谓词预测可能是可取的，并且相对于简单的谓词化，它具有使用动态成本和置信度估计的优势。)

(或许ARM选择在64位AArch64中放弃广泛的谓词化，说明了一些问题。虽然这在指令编码方面占据很大部分，但谓词化对于高性能实现的好处显然相对较低。)

编译器问题

分支代码和无分支代码的性能取决于分支的可预测性和其他因素（包括如果采用，重定向提取的任何惩罚），但编译器很难确定分支的可预测性。即使是配置文件数据通常只提供分支频率，这可能会给出一种悲观的可预测性观点，因为这样不考虑分支预测器使用本地或全局历史记录。编译器也不完全了解数据可用性和其他动态方面的时间。如果条件比用于计算的操作数稍后可用，则将控制依赖（分支预测）替换为数据依赖（预测）可能会降低性能。无分支代码还可能引入更多活跃值，可能会增加寄存器溢出和填充开销。

更进一步的是，大多数仅提供条件移动或选择指令的指令集不提供条件存储。虽然可以通过使用条件移动来选择一个安全的、被忽略的存储位置来解决这个问题，但这似乎是一个不太理想的复杂化。此外，条件移动指令通常比简单的算术指令更昂贵；一个加法和条件移动可能需要三个周期，而正确预测的分支和加法将需要零个周期（如果加法被分支覆盖）或一个周期。

另一个复杂性在于，条件操作通常被分支预测器忽略。如果后续的保留分支与移除分支的条件相关，则该后续分支的分支错误率可能会增加。（可以使用谓词预测来保留这些已移除分支的预测效果。）

随着对矢量化的重视增加，无分支代码的使用变得更加重要，因为基于分支的代码限制了对整个向量进行操作的能力。

- user2467198

---

抱歉内容有些长。我没有涵盖一些可能很有趣的事情，也没有对权衡做出彻底的解释（特别是针对乱序实现），但似乎得到一个不太晚的答案比可能在未来几年内得到更完整和更好组织的答案要好。 - user2467198

Answer 2

现代高性能乱序CPU通常不会在错误预测时刷新整个流水线⁰，但这并不是根据您所建议的分支距离或工作方式进行的。

它们通常使用类似于刷新分支指令和所有更年轻的指令的策略。前端被清空，这将充满错误预测路径上的指令，但超出前端的现代核心可能一次有100多条指令正在执行，其中只有一些可能比分支更年轻。

这意味着分支成本至少在某种程度上与周围指令相关：如果可以早期检查分支条件，则错误预测的影响可以得到限制，甚至可以为零¹。另一方面，如果分支条件是晚处理的，在错误路径上消耗了相当多的资源之后，成本可能很大（例如，大于您经常看到的12-20个周期的“发布”分支错误预测惩罚）。

---

⁰确切的术语在这里存在争议：刷新流水线的含义对于乱序处理器来说并不完全清楚。在这里，我指的是CPU不会刷新所有正在执行但可能没有执行的指令。

¹特别地，对于某些指令序列，限制因素可能是依赖链，其当前执行距离指令窗口的前沿足够远，以至于错误预测不会刷新任何这些指令，并且根本不会减慢代码。

- BeeOnRope

---

是的，错误预测的分支有特殊处理，不像其他异常会清空流水线，因为分支失效很常见。CPU具有回滚缓冲区，在每个条件/间接分支处快照寄存器重命名/其他体系结构状态。(对于每个可能陷入陷阱的指令，如加载/存储，使用它会使其很快填满。)我不知道如果此缓冲区填满是否会正确预测分支吞吐量，如果无法快速检查预测。在微架构讨论中似乎很少被提到。 - Peter Cordes

我相信内存排序误判是一种机器级别的崩溃，而分支预测失误则不是。虽然我不确定其内在机制，但我猜想其效果类似于RAT状态的检查点。根据http://www.ieice.org/proceedings/ITC-CSCC2008/pdf/p233_D3-4.pdf的描述，目前的方法是通过检查点或等待误判分支到达ROB队列的头部（以获取该点的按序状态），但无检查点的方法会慢得多。（该论文提出了一个新想法，但我还没有阅读它。） - Peter Cordes

即使使用基于ROB的重命名（其中提交的值被复制到体系结构寄存器文件中，以便将RAT映射到arch.寄存器），调度程序仍然会有死指令。这些指令可以通过延迟其目的地的释放并像往常一样进行调度而“无害”地执行。或者，可以为错误预测恢复实施快速执行，每个操作立即产生“结果”信号（1个周期执行延迟），甚至可能避免一些结构性危险。这似乎与重播风暴有关。 - user2467198

@PaulA.Clayton：我们知道当前的x86 CPU绝对不会一直等到错误预测的分支准备好才退役。我认为它们会通过快速执行机制从调度器中丢弃陈旧的微操作码（uops）。 （相关：如果标志结果被覆盖而没有读取，SnB可以从可变计数shl eax，cl中丢弃一个标志合并uops，而无需在其上使用执行单元。我在这个答案中引用了英特尔的优化手册3.5.1.6。https://dev59.com/y1oV5IYBdhLWcg3wPctv#36510865） 当然，前端带宽来发出/重命名它是无法恢复的。 - Peter Cordes

@PaulA.Clayton - 这取决于实现方式（正如您提到的分支延迟插槽警告）！这就是我的观点：任何顺序流水线都有一个明显的位置，您可以指出并说“早于此的所有内容都被清除”，有时也会包括一些较新的内容作为实现方便。对于顺序执行来说，细节并不是非常重要，因为差异在几乎任何情况下都意味着多出几个周期/指令。然而，对于OoO，它突然变得非常重要（并且定义很重要），因为我们可能正在讨论数百条指令。 - BeeOnRope

Answer 3

如果预测错误，分支实际上被执行了，那么CPU只需要丢弃流水线中的1条指令（if-body中的一条指令）。

这并不像你所说的那么容易。指令会修改体系结构中的各种状态，其他指令则依赖于这些状态（寄存器结果、条件标志、内存等）。在意识到预测错误之前，可能会有大量已经开始执行的指令，这些指令是基于该指令及其后续指令改变的状态进行执行的...更不用说可能引发故障/异常的指令了。

举个简单的例子：

b = 0
f (a == 0) {
    b = 1;
}
c = b * 10;
if (b == 0)
    printf("\nc = %d.",c);
foo(b);
etc..

要撤销那个“一个简单指令”需要大量的工作。

对于预测性差的简单分支，推荐使用预测/条件移动等方法。

- drivingon9

Answer 4

至少对于大多数处理器而言，一个错误预测的分支会清空整个流水线。

这是为什么（大多数？）现代处理器也提供条件指令的很大一部分原因。

在ARM上，大多数指令都是有条件的，这意味着指令本身可以包含一个条件来表示，“执行X，但仅当以下条件为真时执行”。

同样，最近迭代的x86 / x64也包括一些有条件的指令，例如“CMOV”（条件移动），其工作方式相同--只有在满足条件时才执行指令。

这些指令不会清空流水线--指令本身始终只是通过流水线。如果条件未满足，则该指令基本上没有任何效果。缺点是指令需要执行时间，即使它们没有效果。

因此，在像你所说的这种情况下（一个小体积的if语句），你可以将它们实现为有条件的指令。

如果主体需要足够多的指令（大致等于指令流水线的大小乘以某个常量因子），那么使用条件跳转会更有意义。

- Jerry Coffin