循环"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中的所有位放在一起。即计算奇偶。

从上一条指令(and $1,%eax)开始，我们知道只有低位的结果才重要。

考虑到这一点，xor %edx,%eax变得更清晰了: xor是当前将%edx转换为%eax的低比特。高垃圾并不重要。

shr循环，直到x的所有位都被移除为止。我们总是可以循环32次才能得到所有的位，但这比在x为0时停止的效率要低。(由于XOR的工作方式，我们不需要在0位中实际执行XOR；这是没有效果的。)

一旦我们知道了函数的作用，填充C就变成了一个巧妙/紧凑的C语法练习。起初，我认为y ^= (x>>=1);适合循环，但在第一次使用它之前，这改变了x。

我在一个C语句中看到的唯一方法是使用,操作符(它确实引入了一个序列点，因此在左侧读取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 Gcc5.3 -O3在戈德波特编译器浏览器上的应用。该问题的代码去优化xor-zeroing成语到一个mov $0, %eax，并优化gcc的愚蠢重复的ret指令。(也可能使用了早期版本的gcc，但并没有这么做。)

循环效率很低:这是一种有效的方法：

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

我已经删除了操作数大小的后缀，因为指令是由寄存器决定的.(除了xorw使16位xor显式。)

#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

是的，没错，)是从“根据结果设置标志”的每条指令的低8位更新的，比如xor。

我们使用np条件，因为PF =1表示所有位的偶数奇偶: xor = 0。对于偶数奇偶，我们需要逆返回0。

为了利用它，我们做了一个SIMD式的水平缩减，把上半降低到下半，然后组合，重复两次，将32位减少到8位。

正如我在setp %al中解释的那样，在设置标志的指令之前对eax (使用xor)进行零化比执行set标志/ movzbl %al, %eax / 在x86程序集中将寄存器设置为零的最佳方法是: xor、mov还是and？略高一些。

或者，正如@EOF所指出的，如果CPUID 特征位被设置，您可以使用popcnt并测试低位，以查看设置的位数是偶数还是奇数。(另一种看法是: xor是加-不带进位，所以无论是将所有位放在一起还是将所有位相加在一起，低位都是相同的)。

GNU还具有__builtin_parity和__builtin_popcnt，如果您告诉编译器编译目标支持编译目标(使用-march=...或-mpopcnt)，则它们使用硬件指令，但否则将编译成目标机器的有效序列。英特尔的本质总是编译到机器指令，而不是回退序列，如果没有适当的-mpopcnt目标选项，使用它们是编译时错误。

不幸的是，gcc没有认识到纯C循环是一种奇偶计算，并将其优化为此。有些编译器(比如clang和gcc)可以识别某些流行的成语，并将它们优化到popcnt指令中，但这种模式识别在这种情况下是不可能发生的。:(

看这些在哥德波特上。

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标记wiki中的其他链接。