assembly - 循环 "xorl %edx,%eax; shrl $1,%edx"的目的是什么？

Question

我有以下 x86 汇编代码:

  movl   8(%ebp), %edx  //get an argument from the caller
  movl   $0, %eax
  testl  %edx, %edx
  je     .L1            
.L2:                   // what's the purpose of this loop body?
  xorl   %edx, %eax
  shrl   $1, %edx
  jne    .L2
.L1:
  andl   $1, %eax

教科书给出的对应C代码如下

int f1(unsigned x)
{
    int y = 0;
    while(x != 0) {
        __________;
    }
    return __________;
 }

本书要求读者填空并回答“它有什么作用？”的问题。

我不能在一个 C 表达式中组合循环体。我可以说出循环体的作用，但我不知道它的用途。教科书还说，这里的 %eax 存储了返回值。所以……这样做的目的是什么

andl  $1, %eax

我也不知道。

Answer 1

看起来整个循环的目的是对 32 位 arg 中的所有位进行异或运算。即计算 parity .

从最后一条指令 ( and $1,%eax ) 向后工作，我们知道只有结果的低位才重要。

考虑到这一点，xor %edx,%eax变得更清晰:异或%edx的当前低位进入 %eax .高垃圾无所谓。
shr循环直到所有 x的位已移出。我们总是可以循环 32 次以获取所有位，但这比停止一次效率低 x是 0。(由于 XOR 的工作原理，我们不需要在 0 位中进行实际的 XOR；这没有效果。)

一旦我们知道函数的作用，填充 C 就变成了巧妙/紧凑的 C 语法练习。我一开始以为y ^= (x>>=1);将适合循环内，但转移 x在第一次使用之前。

我在一个 C 语句中看到的唯一方法是使用 ,运算符(它确实引入了 sequence point ，因此可以安全地读取左侧的 x 并在 , 的右侧修改它)。所以，y ^= x, x>>=1;适合。

或者，为了获得更易读的代码，只需作弊并将两个语句与 ; 放在同一行。 .

int f1(unsigned x) {
    int y = 0;
    while(x != 0) {
        y ^= x;  x>>=1;      
    }
    return y & 1;
 }

这将编译为与问题 中显示的基本相同的 asm , 使用 gcc5.3 -O3 on the Godbolt compiler explorer .问题代码 de-optimizes the xor-zeroing idiom到 mov $0, %eax ，并优化了 gcc 对 ret 的愚蠢重复指示。 (或者可能使用了没有这样做的早期版本的 gcc。)

循环非常低效:这是一种有效的方式:

我们不需要复杂度为 O(n) 的循环(其中 n 是以位为单位的宽度 x )。相反，我们可以获得 O(log2(n)) 的复杂度，并且实际上利用 x86 技巧只执行前两个步骤。

对于由寄存器确定的指令，我省略了操作数大小的后缀。 (除了 xorw 使 16 位异或显式。)

#untested
parity:
    # no frame-pointer boilerplate

    xor       %eax,%eax        # zero eax (so the upper 24 bits of the int return value are zeroed).  And yes, this is more efficient than mov $0, %eax
                               # so when we set %al later, the whole of %eax will be good.

    movzwl    4(%esp), %edx      # load low 16 bits of `x`.  (zero-extend into the full %edx is for efficiency.  movw 4(%esp), %dx would work too.
    xorw      6(%esp), %dx       # xor the high 16 bits of `x`
    # Two loads instead of a load + copy + shift is probably a win, because cache is fast.
    xor       %dh, %dl           # xor the two 8 bit halves, setting PF according to the result
    setnp      %al               # get the inverse of the CPU's parity flag.  Remember that the rest of %eax is already zero, so the result is already zero-extended to 32-bits (int return value)
    ret

是的，没错， x86 has a parity flag ( PF )这是从“根据结果设置标志”的每条指令的结果的低 8 位更新的，例如 xor .

我们使用 np条件因为 PF = 1 表示偶校验:所有位的异或 = 0。我们需要反向返回 0 以进行偶校验。

为了利用它，我们通过将高半部分降低到低半部分并合并，重复两次以将 32 位减少到 8 位来进行 SIMD 风格的水平缩减。

在设置标志的指令之前将 eax 归零(使用异或)比设置标志/ setp %al 稍微更有效/ movzbl %al, %eax ，正如我在 What is the best way to set a register to zero in x86 assembly: xor, mov or and? 中解释的那样.

或者，正如@EOF 指出的那样，如果 CPUID POPCNT feature bit is set ，可以使用popcnt测试低位，看看设置的位数是偶数还是奇数。 (另一种看待这个问题的方式:xor 是加无进位，因此无论是将所有位异或还是将所有位水平相加，低位都是相同的)。

GNU C 也有 __builtin_parity和 __builtin_popcnt如果您告诉编译器编译目标支持它(使用 -march=... 或 -mpopcnt )，则使用硬件指令，否则编译为目标机器的有效序列。 Intel 内在函数总是编译为机器指令，而不是回退序列，并且在没有适当的情况下使用它们是编译时错误 -mpopcnt目标选项。

不幸的是，gcc 没有将纯 C 循环识别为奇偶校验计算并将其优化为此。一些编译器(比如 clang 和 gcc)可以识别某些类型的 popcount 习惯用法，并将它们优化为 popcnt指令，但在这种情况下不会发生这种模式识别。 :(

See these on godbolt .

int parity_gnuc(unsigned x) {
    return  __builtin_parity(x);
}
    # with -mpopcnt, compiles the same as below
    # without popcnt, compiles to the same upper/lower half XOR algorithm I used, and a setnp
    # using one load and mov/shift for the 32->16 step, and still %dh, %dl for the 16->8 step.

#ifdef __POPCNT__
#include <immintrin.h>
int parity_popcnt(unsigned x) {
    return  _mm_popcnt_u32(x) & 1;
}
#endif

    # gcc does compile this to the optimal code:
    popcnt    4(%esp), %eax
    and       $1, %eax
    ret

另请参阅 x86 中的其他链接标记维基。