assembly 使用汇编除以2的可变幂

ryoqjall  于 11个月前  发布在  其他
关注(0)|答案(2)|浏览(90)

我有个任务:

dividePower2

计算 x/2n,0 ≤ n ≤ 30。向零舍入。

  • 参数1:x
  • 论据2:n

示例如下:

  • dividePower2(15,1) = 7
  • dividePower2(-33,4) = -2

这就是我到目前为止所得到的,但我不知道我是否朝着正确的方向前进(需要AT&T语法):

.global dividePower2
   dividePower2:
   sar $2, %esi
   ret

字符串

xpszyzbs

xpszyzbs1#

是的,如果你想有效地做的话,算术右移是很有用的。
但是,n >>= 2;并不是一个有用的东西,你所做的任何移位都需要是可变计数的(或者如果你广播符号位来制作一个0 / -1掩码,则需要31)。
看看编译器如何处理一个常量n,比如return x / (1<<11);.(Godbolt)。

# x86-64 GCC -O3
bar(int):
        testl   %edi, %edi        # set FLAGS according to x
        leal    2047(%rdi), %eax
        cmovns  %edi, %eax        # x < 0  ?  x+(1<<11)-1  :  x
        sarl    $11, %eax         # arithmetic right shift that value
        ret                       # return value in EAX

字符串

*一个简单的x >> nsar %cl, %edi)舍入到-Infinity,而不是截断到0。Difference in x/2 and x>>1 or x*2 and x << 1 where x is an integer * 详细介绍了编译器如何为x/2x/8或其他对象实现C除法语义。

加上2047可以将小负数 Package 成小正数,但只有小于1<<11的数字。因此,后面的sar将把所有设置的位移出去,留下0,就像我们想要的除法一样,对于幅度小于2048的原始小负数,向零截断。
对于更大的负数,增加一个正数会减少数量,减少商,除非它是一个精确的倍数。(因为我们增加的1比除数小)。这让我们可以使用sar(算术右移),它向-Infinity舍入,考虑到它和我们想要的截断除法之间的差。
对于一个变量count,return x / (1<<n),编译器简单地将1<<n具体化并使用idiv。但是我们可以通过遵循与2的常数幂的有符号除法相同的模式来做得更好。
(The [0,30]中的n范围限制意味着1<<31溢出到INT_MIN是没有问题的。我认为这个算法可以正确地用于n=31。结果是0-1,这是32位sar乘31的两个可能结果。将0x7fffffff与除INT_MIN = 0x 80000000之外的任何负数相加将产生非负数,所以sar产生0。对于x = INT_MIN,我们执行-1 >> 31得到-1。)
我们可以做x + (1<<n)-1,并使用相同的测试/cmovns得到xx + (1<<n)-1-1部分可以作为莱亚的一部分来完成。
在Intel CPU上获取1<<n的最有效方法是将bts放入一个置零寄存器。(变量计数shl为3 uops,除非我们使用BMI 2 sarx。使用xor实现0mov $1, %eax便宜。)在AMD Zen上,bts是2个uops,但shl %cl, %eax只有1个uops(https://uops.info),将1移到EAX和shl中可能更便宜,因为我们无论如何都需要CL中的移位计数用于后面的sar。(除非我们有sarx的BMI 2,它允许移位计数来自任何寄存器。)
另一种选择是通过将BMI2 bzhi应用于0xffffffff来获得(1<<n) - 1;我认为这直接适用于[0,32]范围内的n(尽管sar仍然只适用于n=[0,31])。它在Intel和AMD上是单uop(https://uops.info/)。见下文;这就是clang对C版本的作用。

# untested
.global dividePower2         # int x in EDI,  int n in ESI
                             # returns int in EAX
dividePower2:
   xor   %eax, %eax
   bts   %esi, %eax             # 2^n = 1<<n
   lea   -1(%rax, %rdi), %eax   # x + 2^n - 1

   test  %edi, %edi
   cmovns %edi, %eax     # x for non-negative,  x + 2^n - 1 for negative

   mov   %esi, %ecx      # or  sarx %esi, %eax, %eax
   sar   %cl, %eax       # >>= n  on the adjusted value is equivalent to /= (1>>n)
   ret


具有3个组件的莱亚([-1 + rax + rdi])在Skylake和更早版本上会有3个周期的延迟,但Ice Lake运行它有1个周期的延迟。Ice Lake和更高版本上的“慢”LEA不能在那么多端口上运行,但没有延迟损失。(在桤木Lake P-core上,scaled index像Zen系列一样花费2个周期延迟,即使它只是一个2组件莱亚,但我们没有在这里缩放索引。)在Zen-family上,这个3组件莱亚有2个周期延迟。在桤木Lake E-core上也是如此。所以用单独的adddec指令来做没有什么可保存的。
另一种获取(1<<n) - 1的方法是旧的clang所做的:0xffffffff >> (-n&31)。它实际上从sar $31, reg生成0xffffffff0来广播符号位。但是这种策略对于变量n不太方便,因为它需要求反。在没有BMI 2的x86上尤其不方便,因为移位计数需要在CL中。
应该可以使用SSE 2 pslldpsrad的SIMD版本,或者使用每个元素变量计数的AVX 2 vpsllvd
与SSE4.1 pblendvps混合可以替代标量cmov,但似乎应该可以更高效。也许使用psrad来获取0-1并做一些事情会更好?或者只是使用它作为pandn的掩码,在x为非负的元素中将1<<n - 1向量置零。psrad结果直接用作(1<<n) - 1中的-1

在C或C++中

// well-defined behaviour for n=0..30
int divp2_bitshift(int x, int n){
    int bias = x < 0 ? (1U<<n)-1 : 0U;
    return (x+bias) >> n;
// To handle n=31, use  unsigned bias  and cast x+bias  back to signed int to avoid signed-overflow UB
// That might depend on int being 2's complement, so C++20 or C23
}

int divp2_reference(int x, int n){
    return x / (1LL<<n);  // 64-bit shift and division avoids overflow to INT_MIN
}


Clang -march=skylake使用bzhi巧妙地编译为优化版本:

# clang -O3 -march=skylake (BM1 and BMI2)
bitshift(int, int):
        movl    %edi, %eax
        sarl    $31, %eax            # 00000000 or FFFFFFFF
        bzhil   %esi, %eax, %eax     # 0 or (1<<n)-1 

        addl    %edi, %eax
        sarxl   %esi, %eax, %eax
        retq


Godbolt,包括一个main,用于针对每个int32_t位模式和从031的每个n,对参考版本和优化版本进行详尽测试。它通过了所有情况。

如果参考实现是return x / (1<<n),则它对所有n=0..30都通过,但对-2147483648 / (1<<31) = 1则失败(因为参考实现中的1<<31溢出到INT_MIN,但移位版本给出-1,因为它除以2的正幂。)我用gcc -O3 -fwrapv -march=native编译,使有符号整数溢出良好-为了便于测试ASM而定义。
因此,这种优化对于x/(1<<n)gcc -fwrapv是不可用的,因为n=31的行为被定义为具有负除数。
但是如果没有-fwrapv,其中有符号溢出在C中是未定义的行为,那么这种优化将是有效的。TODO:向GCC和clang报告这种错过的优化。
对于n=0..31的x/(1LL<<n)也是有效的,但对于n=32或更高的n则不有效,因为这在C中仍然是定义良好的(我假设x是32位的int,所以long long更宽; n=32..63是有效的,并且使商为0)。

oiopk7p5

oiopk7p52#

你需要在计算中使用IEEE标准的浮点数。这会占用更多的内存,但我看不出有任何其他方法。
记住,任何浮点数都可以写成:
S| exp比特|分数位
设n1=x = s_x| exp bits_x|分数位x
n2=2^n 0| B(n+127)|0
n1/n2等于s_x| exp bits_x-b(n+127)|分数位x
您需要2个32位寄存器来存储除数和除数,1个32位寄存器用于结果。

相关问题