c++ - VS : unexpected optimization behavior with _BitScanReverse64 intrinsic

Question

以下代码在 Debug模式下工作正常，因为定义了 _BitScanReverse64如果没有设置 Bit 则返回 0。 Citing MSDN :(返回值是)“如果设置了索引则为非零，如果未找到设置位则为 0。”

如果我在 Release模式下编译这段代码它仍然有效，但如果我启用编译器优化，例如\O1 或\O2 索引不为零并且 assert() 失败。

#include <iostream>
#include <cassert>

using namespace std;

int main()
{
  unsigned long index = 0;
  _BitScanReverse64(&index, 0x0ull);

  cout << index << endl;

  assert(index == 0);

  return 0;
}

这是预期的行为吗？我正在使用 Visual Studio Community 2015，版本 14.0.25431.01 Update 3。(我留下了 cout，以便在优化过程中不会删除变量索引)。还有一种有效的解决方法，还是我不应该直接使用这个编译器内部函数？

Answer 1

AFAICT，当输入为零时，内在函数会在 index 中留下垃圾， 弱于 asm 指令的行为。这就是为什么它有一个单独的 bool 返回值和整数输出操作数。

尽管 index arg 被引用，编译器将其视为仅输出。

---

unsigned char _BitScanReverse64(unsigned __int32* 索引，unsigned __int64 掩码)
Intel's intrinsics guide documentation for the same intrinsic似乎比 Microsoft docs 更清晰您已链接，并阐明了 MS 文档试图表达的内容。但仔细阅读，它们似乎都在说同样的事情，并描述了 bsr 指令的薄包装。

Intel documents the BSR instruction当输入为 0 时产生“未定义值”，但在这种情况下设置 ZF。 但 AMD 将其记录为保持目标不变:

AMD's BSF entry in AMD64 Architecture Programmer’s Manual Volume 3: General-Purpose and System Instructions

... If the second operand contains 0, the instruction sets ZF to 1 and does not change the contents of the destination register. ...

在当前的 Intel 硬件上，实际行为与 AMD 的文档相符:当 src 操作数为 0 时，它不修改目标寄存器。也许这就是为什么 MS 将其描述为仅在输入为时设置 Index非零(并且内部函数的返回值非零)。

在英特尔 ( but maybe not AMD ) 上，这甚至没有将 64 位寄存器截断为 32 位。例如mov rax,-1 ; bsf eax, ecx(ECX 归零)使 RAX=-1(64 位)，而不是 0x00000000ffffffff 您从 xor eax, 0。但是对于非零 ECX，bsf eax, ecx 具有零扩展到 RAX 的通常效果，例如 RAX=3。

---

IDK 为什么 Intel 仍然没有记录它。 也许一个非常老的 x86 CPU(比如原来的 386？)以不同的方式实现它？ Intel和AMD频频go above and beyond what's documented in the x86 manuals in order to not break existing widely-used code (e.g. Windows) ，这可能就是这样开始的。

在这一点上，英特尔似乎不太可能放弃该输出依赖性并为输入 = 0 保留实际垃圾或 -1 或 32，但缺乏文档使该选项处于打开状态。

Skylake 删除了对 lzcnt 和 tzcnt 的虚假依赖(后来的 uarch 删除了对 popcnt 的虚假依赖)，同时仍然保留了依赖对于 bsr/bsf。 ( Why does breaking the "output dependency" of LZCNT matter? )

---

当然，由于 MSVC 优化了您的 index = 0 初始化，大概它只是使用它想要的任何目标寄存器，不一定是保存 C 变量先前值的寄存器。 因此，即使您愿意，我也不认为您可以利用 dst-unmodified 行为，即使它在 AMD 上得到保证。

因此，在 C++ 术语中，内在函数对 index 没有输入依赖性。但是在 asm 中，指令确实对 dst 寄存器有输入依赖性，就像 add dst, src 指令一样。如果编译器不小心，这可能会导致意外的性能问题。

不幸的是，在 Intel 硬件上，popcnt / lzcnt / tzcnt asm instructions also have a false dependency on their destination ，即使结果从不依赖于它。不过，编译器现在已经知道了这个问题，因此您在使用内在函数时不必担心它(除非您的编译器已经使用了几年以上，因为它是最近才发现的)。

---

您需要检查它以确保 index 有效，除非您知道输入不为零。例如

if(_BitScanReverse64(&idx, input)) {
    // idx is valid.
    // (MS docs say "Index was set")
} else {
    // input was zero, idx holds garbage.
    // (MS docs don't say Index was even set)
    idx = -1;     // might make sense, one lower than the result for bsr(1)
}

---

如果你想避免这个额外的检查分支，你可以使用 lzcnt instruction如果您的目标是足够新的硬件(例如 Intel Haswell 或 AMD Bulldozer IIRC)，则通过不同的内在函数。即使输入全为零，它也“有效”，并且实际上计算前导零而不是返回最高设置位的索引。