x86 BSR/BSF如何具有固定的延迟，而不是依赖于数据？它不是像伪代码显示的那样在位上循环吗？

Question

我准备分析一些x86二进制代码的一些“定时通道”。我提出一个问题来理解BSF/BSR操作码。

IF SRC = 0
  THEN
    ZF ← 1;
    DEST is undefined;
  ELSE
    ZF ← 0;
    temp ← OperandSize – 1;
    WHILE Bit(SRC, temp) = 0
    DO
      temp ← temp - 1;
    OD;
    DEST ← temp;
FI;

那为什么有可能呢？显然，这是一个“循环”，或者在某种程度上，至少是高层次的。背后的设计决策是什么？对于CPU管道更容易？

Answer 1

BSF/BSR性能不依赖于任何现代CPU。有关实验计时结果，请参见https://agner.org/optimize/、https://uops.info/（仅Intel）或http://instlatx64.atw.hu/以及https://gmplib.org/~tege/x86-timing.pdf。

在现代Intel上，它们解码为1个uop，具有3个周期的延迟和1/时钟的吞吐量，仅在端口1上运行。Ryzen还在BSF中使用3C延迟，BSR中使用4C延迟，但有多个UOP。早期的AMD有时甚至更慢。

您的“8周期”（延迟和吞吐量）成本似乎是32位BSF在AMD K8上，从Granlund的表，你链接。Agner Fog的表格同意这一观点（并显示它解码为21个uops，而不是有一个专用的位扫描执行单元。但微编码的实现可能仍然是无分支的，不依赖于数据）。不知道你为什么选那个号码；K8没有SMT/超线程，所以ALU定时侧通道的机会大大减少。

（在intrinsics中利用这一点是不可能的；即使在MSVC的_bitscanReverse64中也是如此，它使用可以先设置的按引用输出arg。MSVC不尊重前面的值，并假定它是只输出的。vs:_bitscanReverse64 intrinsic的意外优化行为）

（也就是说，这不一定是硬件或微代码的工作方式）。

它在所有情况下都给出了完全相同的结果，所以您可以使用它来准确地理解文本中让您想知道的任何角落情况下会发生什么。仅此而已。

整数加法可以建模为位串行纹波进位，但这不是它的实现方式！相反，我们使用进位查找加法器等技巧，以远小于64门延迟获得64位加法的单周期延迟。

在美国专利US8214414 B2中描述了Intel的位扫描/popcnt执行单元中使用的实际实现技术。

摘要

AMD可能会做一些不同的事情，但不管怎样，我们从性能实验中知道，它不依赖于数据。

众所周知，固定延迟对于无序调度是一个非常有益的东西，所以当指令没有固定延迟时，这是非常令人惊讶的。Sandybridge甚至对延迟进行了标准化，以简化调度程序并减少写回冲突的机会（例如，对同一端口进行3周期延迟uop和2周期延迟uop将在同一周期内产生2个结果）。这意味着使complex-LEA（包含所有3个组件:[disp+base+idx*scale])需要3个周期，而不是像以前的CPU那样，两个添加过程只需要2个周期。在SandyBridge-family上没有2周期延迟uops。（有一些2周期延迟指令，因为它们解码为2个UOP，每个UOP1C延迟，但是调度器调度UOP，而不是指令）。

对于ALU uops来说，固定延迟规则的少数例外之一是division/sqrt，它使用一个不完全流水线的执行单元。除法本质上是迭代的，与乘法不同，在乘法中，您可以使用广泛的硬件并行地进行部分乘积和部分加法。

在Intel CPU上，L1d缓存访问的可变延迟可以在调度器乐观地希望数据没有准备好的情况下产生相关UOP的回放。

• 当base+偏移量位于与base不同的页面时，是否会有损失？
• 为什么每次迭代的UOP数量会随着流负载的增加而增加？
• 在Ivybridge上的指针追逐循环中，附近的依赖存储会产生奇怪的性能影响。添加额外的负载可以加快速度？