x86 bsr/bsf 如何具有固定的延迟，而不依赖于数据？它不会像伪代码所示那样遍历位吗？
How can x86 bsr/bsf have fixed latency, not data dependent? Doesn't it loop over bits like the pseudocode shows?
我正忙着分析一些 "timing channels" 的一些 x86 二进制代码。我发布了一个问题来理解 bsf/bsr 操作码。
在高层，这两个操作码可以建模为 "loop"，它计算给定操作数的前导零和尾随零。 x86 手册对这些操作码进行了很好的形式化，如下所示：
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;
但令我惊讶的是，bsf/bsr 指令似乎有 固定的 cpu 周期 。根据我在这里找到的一些文件：https://gmplib.org/~tege/x86-timing.pdf，似乎他们总是需要 8 CPU 个周期才能完成。
所以这是我的问题：
我确认这些指令具有固定的 cpu 周期。也就是说，不管给什么操作数，他们处理的时间总是一样的，后面没有"timing channel"。我在Intel的官方文档中找不到对应的规格。
那为什么可以呢？显然这是一个 "loop" 或某种程度上，至少是高层次的。背后的设计决策是什么？ CPU 管道更容易？
BSF/BSR 性能不依赖于任何现代 CPUs 的数据。 请参阅您发现的 https://agner.org/optimize/, https://uops.info/ (Intel only), or http://instlatx64.atw.hu/ for experimental timing results, as well as the https://gmplib.org/~tege/x86-timing.pdf。
在现代 Intel 上，它们解码为 1 uop，具有 3 个周期延迟和 1/clock 吞吐量，运行 仅在端口 1 上。Ryzen 也以 3c 延迟 BSF，4c 延迟 BSR 运行它们，但是多个微调。早期的 AMD 有时甚至更慢。
您的“8 周期”（延迟 和 吞吐量）成本似乎是针对 AMD K8 上的 32 位 BSF，来自您链接的 Granlund table。 Agner Fog 的 table 同意，（并显示它解码为 21 微指令而不是具有专用的位扫描执行单元。但微编码实现可能仍然是无分支的并且不依赖于数据）。不知道你为什么选择 那个 号码； K8 没有 SMT / 超线程，因此 ALU 时序侧通道的机会大大减少。
请注意，它们对目标寄存器有输出依赖性，如果输入为零，它们将保持不变。AMD 记录了这种行为，英特尔在硬件中实现了它，但是 documents it as an "undefined" result，所以不幸的是编译器不会利用它，人类程序员可能应该谨慎。 IDK 如果一些古老的 32 位 CPU 有不同的行为，或者如果英特尔计划永远改变（怀疑！），但我希望英特尔至少记录 64 位模式的行为（不包括任何旧的CPUs).
lzcnt/tzcnt 和 popcnt on Intel CPUs（但不是 AMD）在 Skylake 和 Cannon Lake 之前（分别）具有相同的输出依赖性，即使在架构上，所有输入的结果都是明确定义的。它们都使用相同的执行单元。 ()。 AMD Bulldozer/Ryzen 构建了他们的位扫描执行单元而没有内置输出依赖性，因此 BSF/BSR 比 LZCNT/TZCNT 慢（多个 uops 来处理 input=0 的情况，并且可能还设置 ZF根据输入，而不是结果）。
（利用内在函数是不可能的；即使使用 MSVC 的 _BitScanReverse64 也是如此，它使用您可以首先设置的引用输出 arg。MSVC 不尊重先前的值并假定它仅用于输出。)
手册中的伪代码不是实现
（即不一定是硬件或 微码 的工作方式）。
它在所有情况下都给出完全相同的结果，因此您可以使用它来准确了解文本让您想知道的任何极端情况会发生什么。即全部.
重点是简单易懂，这意味着根据连续发生的简单 2 输入操作对事物进行建模。 C / Fortran / 典型的伪代码不有用于多输入 AND、OR 或 XOR 的运算符，但您可以在硬件中构建它直到某个点（limited by fan-in，与扇出相反）。
整数加法 可以 建模 作为位串行纹波进位，但这不是它的实现方式！相反，我们使用 carry lookahead adders.
等技巧获得 64 位加法的单周期延迟，门延迟远少于 64 个
Intel的位扫描/popcnt执行单元实际使用的实现技术在US Patent US8214414 B2.
中有描述
Abstract
A merged datapath for PopCount and BitScan is described. A hardware
circuit includes a compressor tree utilized for a PopCount function,
which is reused by a BitScan function (e.g., bit scan forward (BSF) or
bit scan reverse (BSR)).
Selector logic enables the compressor tree to
operate on an input word for the PopCount or BitScan operation, based
on a microprocessor instruction. The input word is encoded if a
BitScan operation is selected.
The compressor tree receives the input
word, operates on the bits as though all bits have same level of
significance (e.g., for an N-bit input word, the input word is treated
as N one-bit inputs). The result of the compressor tree circuit is a
binary value representing a number related to the operation performed
(the number of set bits for PopCount, or the bit position of the first
set bit encountered by scanning the input word).
可以相当安全地假设英特尔的实际芯片与此类似。诸如无序机器（ROB、RS）之类的其他英特尔专利往往与我们可以执行的性能实验相匹配。
AMD 可能会做一些不同的事情，但不管我们从性能实验中知道它与数据无关。
众所周知，固定延迟对于乱序调度非常有益，所以当指令时非常令人惊讶 没有固定延迟。 Sandybridge 甚至将延迟标准化以简化调度程序并减少写回冲突的机会（例如 3 周期延迟 uop 后跟 2 -cycle latency uop 到同一个端口将在同一个周期中产生 2 个结果）。这意味着使复杂的 LEA（具有所有 3 个组件：[disp + base + idx*scale]）需要 3 个周期，而不是像之前的 CPU 那样只需要 2 个周期来进行 2 次添加。 Sandybridge 系列上没有 2 周期延迟微指令。 （有一些 2 周期延迟指令，因为它们解码为 2 微指令，每个指令有 1c 延迟，但调度程序调度微指令，而不是指令）。
ALU uops 固定延迟规则的少数例外之一是除法/sqrt，它使用非完全流水线化的执行单元。除法本质上是迭代的，与乘法不同，乘法可以制作并行执行部分乘积和部分加法的宽硬件。
在 Intel CPUs 上，如果数据在调度程序乐观地希望准备就绪时尚未准备就绪，则 L1d 缓存访问的可变延迟会产生相关 uops 的重放。
80x86 手册对预期行为进行了很好的描述，但这与它在任何制造商的任何型号的芯片中的实际实现方式无关。
假设有 50 种不同的 CPU 设计来自 Intel，25 种 CPU 设计来自 AMD，然后还有 25 种来自其他制造商（VIA、Cyrix、SiS/Vortex、NSC、 ...）。在这 100 种不同的 CPU 设计中，可能 BSF 有 20 种完全不同的实现方式，其中可能有 10 种具有固定时序，5 种具有取决于源操作数的每一位的时序，和 5 取决于源操作数的位组（例如，可能像 "if highest 32 bits of 64-bit operand are zeros { switch to 32-bit logic that's 2 cycles faster }"）。
I am confirming that these instructions have fixed cpu cycles. In other words, no matter what operand is given, they always take the same amount of time to process, and there is no "timing channel" behind. I cannot find corresponding specifications in Intel's official documents.
你不能。更具体地说，您可以测试或研究现有的 CPU，但这是浪费时间，因为下周 Intel（或 AMD 或 VIA 或其他公司）可能会发布具有完全不同时序的新 CPU。
一旦你依赖"measured from existing CPUs"你就错了。你必须依赖适用于所有未来的"architectural guarantees"CPU秒。没有"architectural guarantee"。 您必须假设可能存在定时边信道（即使当前 CPUs 没有）
Then why it is possible? Apparently this is a "loop" or somewhat, at least high-levelly. What is the design decision behind? Easier for CPU pipelines?
与其做一个 64 位的 BSF，为什么不把它分成一对 32 位的部分并并行地做，然后合并结果呢？为什么不把它分成八个 8 位块呢？为什么不对每个 8 位片使用 table 查找？
贴出的答案已经很好的说明了实现与伪代码不同。但是，如果您仍然好奇为什么延迟是固定的而不依赖于数据或为此使用任何循环，那么您需要了解电子方面的问题。
在硬件中实现此功能的一种方法是使用 Priority encoder。
优先级编码器将接受 n 个可以为 1 或关闭（0 或 1）的输入线，并给出打开的最高优先级线的索引。下面是链接的维基百科文章中的 table 修改为最重要的设置位功能。
input | output index of first set bit
0000 | xx undefined
0001 | 00 0
001x | 01 1
01xx | 10 2
1xxx | 11 3
x 表示位值无关紧要，可以是任何值
如果你看文章上的电路图，没有任何回路，都是并联的。
我正忙着分析一些 "timing channels" 的一些 x86 二进制代码。我发布了一个问题来理解 bsf/bsr 操作码。
在高层，这两个操作码可以建模为 "loop"，它计算给定操作数的前导零和尾随零。 x86 手册对这些操作码进行了很好的形式化，如下所示：
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;
但令我惊讶的是，bsf/bsr 指令似乎有 固定的 cpu 周期 。根据我在这里找到的一些文件：https://gmplib.org/~tege/x86-timing.pdf，似乎他们总是需要 8 CPU 个周期才能完成。
所以这是我的问题：
我确认这些指令具有固定的 cpu 周期。也就是说，不管给什么操作数，他们处理的时间总是一样的，后面没有"timing channel"。我在Intel的官方文档中找不到对应的规格。
那为什么可以呢？显然这是一个 "loop" 或某种程度上，至少是高层次的。背后的设计决策是什么？ CPU 管道更容易？
BSF/BSR 性能不依赖于任何现代 CPUs 的数据。 请参阅您发现的 https://agner.org/optimize/, https://uops.info/ (Intel only), or http://instlatx64.atw.hu/ for experimental timing results, as well as the https://gmplib.org/~tege/x86-timing.pdf。
在现代 Intel 上，它们解码为 1 uop，具有 3 个周期延迟和 1/clock 吞吐量，运行 仅在端口 1 上。Ryzen 也以 3c 延迟 BSF，4c 延迟 BSR 运行它们，但是多个微调。早期的 AMD 有时甚至更慢。
您的“8 周期”（延迟 和 吞吐量）成本似乎是针对 AMD K8 上的 32 位 BSF，来自您链接的 Granlund table。 Agner Fog 的 table 同意，（并显示它解码为 21 微指令而不是具有专用的位扫描执行单元。但微编码实现可能仍然是无分支的并且不依赖于数据）。不知道你为什么选择 那个 号码； K8 没有 SMT / 超线程，因此 ALU 时序侧通道的机会大大减少。
请注意，它们对目标寄存器有输出依赖性，如果输入为零，它们将保持不变。AMD 记录了这种行为，英特尔在硬件中实现了它，但是 documents it as an "undefined" result，所以不幸的是编译器不会利用它，人类程序员可能应该谨慎。 IDK 如果一些古老的 32 位 CPU 有不同的行为，或者如果英特尔计划永远改变（怀疑！），但我希望英特尔至少记录 64 位模式的行为（不包括任何旧的CPUs).
lzcnt/tzcnt 和 popcnt on Intel CPUs（但不是 AMD）在 Skylake 和 Cannon Lake 之前（分别）具有相同的输出依赖性，即使在架构上，所有输入的结果都是明确定义的。它们都使用相同的执行单元。 (
（利用内在函数是不可能的；即使使用 MSVC 的 _BitScanReverse64 也是如此，它使用您可以首先设置的引用输出 arg。MSVC 不尊重先前的值并假定它仅用于输出。
手册中的伪代码不是实现
（即不一定是硬件或 微码 的工作方式）。
它在所有情况下都给出完全相同的结果，因此您可以使用它来准确了解文本让您想知道的任何极端情况会发生什么。即全部.
重点是简单易懂，这意味着根据连续发生的简单 2 输入操作对事物进行建模。 C / Fortran / 典型的伪代码不有用于多输入 AND、OR 或 XOR 的运算符，但您可以在硬件中构建它直到某个点（limited by fan-in，与扇出相反）。
整数加法 可以 建模 作为位串行纹波进位，但这不是它的实现方式！相反，我们使用 carry lookahead adders.
等技巧获得 64 位加法的单周期延迟，门延迟远少于 64 个Intel的位扫描/popcnt执行单元实际使用的实现技术在US Patent US8214414 B2.
中有描述Abstract
A merged datapath for PopCount and BitScan is described. A hardware circuit includes a compressor tree utilized for a PopCount function, which is reused by a BitScan function (e.g., bit scan forward (BSF) or bit scan reverse (BSR)).
Selector logic enables the compressor tree to operate on an input word for the PopCount or BitScan operation, based on a microprocessor instruction. The input word is encoded if a BitScan operation is selected.
The compressor tree receives the input word, operates on the bits as though all bits have same level of significance (e.g., for an N-bit input word, the input word is treated as N one-bit inputs). The result of the compressor tree circuit is a binary value representing a number related to the operation performed (the number of set bits for PopCount, or the bit position of the first set bit encountered by scanning the input word).
可以相当安全地假设英特尔的实际芯片与此类似。诸如无序机器（ROB、RS）之类的其他英特尔专利往往与我们可以执行的性能实验相匹配。
AMD 可能会做一些不同的事情，但不管我们从性能实验中知道它与数据无关。
众所周知，固定延迟对于乱序调度非常有益，所以当指令时非常令人惊讶 没有固定延迟。 Sandybridge 甚至将延迟标准化以简化调度程序并减少写回冲突的机会（例如 3 周期延迟 uop 后跟 2 -cycle latency uop 到同一个端口将在同一个周期中产生 2 个结果）。这意味着使复杂的 LEA（具有所有 3 个组件：[disp + base + idx*scale]）需要 3 个周期，而不是像之前的 CPU 那样只需要 2 个周期来进行 2 次添加。 Sandybridge 系列上没有 2 周期延迟微指令。 （有一些 2 周期延迟指令，因为它们解码为 2 微指令，每个指令有 1c 延迟，但调度程序调度微指令，而不是指令）。
ALU uops 固定延迟规则的少数例外之一是除法/sqrt，它使用非完全流水线化的执行单元。除法本质上是迭代的，与乘法不同，乘法可以制作并行执行部分乘积和部分加法的宽硬件。
在 Intel CPUs 上，如果数据在调度程序乐观地希望准备就绪时尚未准备就绪，则 L1d 缓存访问的可变延迟会产生相关 uops 的重放。
80x86 手册对预期行为进行了很好的描述，但这与它在任何制造商的任何型号的芯片中的实际实现方式无关。
假设有 50 种不同的 CPU 设计来自 Intel，25 种 CPU 设计来自 AMD，然后还有 25 种来自其他制造商（VIA、Cyrix、SiS/Vortex、NSC、 ...）。在这 100 种不同的 CPU 设计中，可能 BSF 有 20 种完全不同的实现方式，其中可能有 10 种具有固定时序，5 种具有取决于源操作数的每一位的时序，和 5 取决于源操作数的位组（例如，可能像 "if highest 32 bits of 64-bit operand are zeros { switch to 32-bit logic that's 2 cycles faster }"）。
I am confirming that these instructions have fixed cpu cycles. In other words, no matter what operand is given, they always take the same amount of time to process, and there is no "timing channel" behind. I cannot find corresponding specifications in Intel's official documents.
你不能。更具体地说，您可以测试或研究现有的 CPU，但这是浪费时间，因为下周 Intel（或 AMD 或 VIA 或其他公司）可能会发布具有完全不同时序的新 CPU。
一旦你依赖"measured from existing CPUs"你就错了。你必须依赖适用于所有未来的"architectural guarantees"CPU秒。没有"architectural guarantee"。 您必须假设可能存在定时边信道（即使当前 CPUs 没有）
Then why it is possible? Apparently this is a "loop" or somewhat, at least high-levelly. What is the design decision behind? Easier for CPU pipelines?
与其做一个 64 位的 BSF，为什么不把它分成一对 32 位的部分并并行地做，然后合并结果呢？为什么不把它分成八个 8 位块呢？为什么不对每个 8 位片使用 table 查找？
贴出的答案已经很好的说明了实现与伪代码不同。但是，如果您仍然好奇为什么延迟是固定的而不依赖于数据或为此使用任何循环，那么您需要了解电子方面的问题。 在硬件中实现此功能的一种方法是使用 Priority encoder。
优先级编码器将接受 n 个可以为 1 或关闭（0 或 1）的输入线，并给出打开的最高优先级线的索引。下面是链接的维基百科文章中的 table 修改为最重要的设置位功能。
input | output index of first set bit
0000 | xx undefined
0001 | 00 0
001x | 01 1
01xx | 10 2
1xxx | 11 3
x 表示位值无关紧要，可以是任何值
如果你看文章上的电路图，没有任何回路，都是并联的。