如何让BSR指令在64位上工作？

Question

我正在尝试找到无符号 64 位 int 的前导位。我正在使用 BSR，因为我的处理器没有 LZCNT 指令。我的问题是，一旦输入正好是 2^32，它就会返回 2^64 作为前导位值，然后循环返回输出，直到 2^64。

这是我的代码：

unsigned long int LeadingBit(unsigned long int a) {
  if(a==0)
    return 0;
  unsigned long int nlb;
  asm (
       "BSR %1, %0   \n"
       : "=r" (nlb)
       : "mr" (a)
       : "cc"
       );
  return 1<<nlb;

}

这段代码的目的是能够输入一个64位整数，并让它返回前导1的位置的值。例如：a = 65（1000001）返回1000000。

Answer 1

虽然迈克尔/弗洛里安的解决方案可能是最简单的，但也许不是最好的。

您现有的代码（用 1UL 修改）编译如下：

    xor     eax, eax
    test    rdi, rdi
    je      .L1
    mov     eax, 1
    BSR rdi, rcx   

    sal     rax, cl
.L1:
    ret

不错，但不是测试零，然后调用 BSR（它也检查零），怎么样：

unsigned long int LeadingBit(unsigned long int a) {

  unsigned long int nlb;
  bool z;
  asm (
       "BSR %[a], %[nlb]"
       : [nlb] "=r" (nlb), "=@ccz"(z)
       : [a] "mr" (a)
       );

    unsigned long int one;
    if (!z)
       one = 1;
    else
       one = 0;

    return one << nlb;
}

由于 BSR 将 ZF 设置为指示零，因此此代码使用它来设置one为 0 或 1，具体取决于。这个 asm 非常干净（gcc 9.2 -O2）：

BSR rdi, rcx
setne   al
movzx   eax, al
sal     rax, cl
ret

“=@ccz”约束在Flag Output Operands下的文档中进行了描述。基本上它只是说“这个变量的值取自 Z (C)ondition (C)ode”。

编辑：看到彼得提供观察结果我并不感到惊讶，但令我惊讶的是他没有发布自己的替代方案。

这是我尝试将他的评论转化为代码的尝试。这可能比OP感兴趣的更复杂，但为了完整起见：

unsigned long int LeadingBit(unsigned long int a) {

  unsigned long int bit;
  unsigned long int res;
  asm (
       "BSR %[a], %[bit]  \n\t"  // sets both (bit) and ZF
       "BTS %[bit], %[res] \n\t" // sets the corresponding bit in (res) and
                                 // carry flag, but *doesn't* change ZF
       "CMOVZ %[zero], %[res]"   // reset res to 0 if BSR detected a==0
       : [bit] "=&r" (bit), [res] "=&r"(res)
       : [a] "mr" (a), [zero] "r"(0UL), "[res]"(0UL)
       : "cc"
       );

    return res;
}

虽然 BSR/BTS/CMOVZ 非常简单，但带有约束的废话可能会让代码的维护者感到困扰。

所以，解释一下发生了什么。

• "=&r"(res)将保存返回值。&用于指示它不能与任何其他参数共享寄存器。需要明确的是，仅仅因为您将约束声明为“=r”，并不意味着您将获得唯一的寄存器，除非您使用&. 减少使用的寄存器数量可能是一件好事，但在本例中情况并非如此。如果编译器决定对 %[zero] 和 %[res] 使用相同的寄存器，则会导致 CMOVZ 失败。
• 说明"[res]"(0UL)在进入 asm 时，无论用于 %[res] 的寄存器都应初始化为零。是的，我们可以在 asm 中执行此操作，但通过将其放入 C 代码中，它允许编译器以相对于周围代码最有效的任何方式执行此操作。哎呀，它可能已经有一个归零的寄存器，它只是用于其他用途。
• BTS让您直接设置寄存器中的位数。它通常比使用更快SAL（这就是 Peter 所说的 SAL 的“3 uops”与 BTS 的 1 uops），但与 BSR 一样，gcc 没有内部函数。虽然它确实返回进位标志中指定位的现有值（这就是 BTS 的 T 部分的含义），但它不会修改零标志。这使得我们在 BTS 之后仍然可以进行 CMOVZ。在某些处理器上以这种方式更新标志寄存器的“部分”可能效率低下，但对于较新的处理器则效率不高。

这是输出：

    xorl    %edx, %edx
    movq    %rdx, %rax
    BSR %rdi, %rcx  
    BTS %rcx, %rax 
    CMOVZ %rdx, %rax
    ret

我对此有点怀疑movq（为什么不xor呢movl？），但我确信这是有充分理由的。我认为与“别名”有关。

如果 perf 的优先级足够高（尽管OP从未说过），那么我还可以考虑做一件事。如果 LeadBit 可能使用常量调用，则编译器通常可以在编译时（而不是在运行程序时）预先计算围绕该常量的大量数学运算。

但是，gcc无法通过内联汇编进行预先计算。如果可以使用常量调用 LeadBit，您可以将我在此处显示的代码包装起来if (__builtin_constant_p(a))以查看是否a是常量，并使用 __builtin_clzll 等人以“慢”方式计算它。我说“慢”，但是在编译时计算值（即使是慢速方式）将导致更快的可执行文件。并且由于（根据定义）__builtin_constant_p 的值在编译时已知，因此if对于LeadingBit 的任何调用都只会生成一个分支。