Aid*_*n M 0 assembly bit-manipulation x86-64 bit-shift integer-division
我有这个任务：
\n\n\n除幂2
\n计算x /2 n，对于 0 \xe2\x89\xa4 n \xe2\x89\xa4 30。向零舍入。
\n\n
\n- 论点1：
\nx- 论据2：
\nn例子：
\n\n
\n- \n
dividePower2(15,1) = 7- \n
dividePower2(-33,4) = -2
这是我到目前为止所得到的，但我不知道我是否朝着正确的方向前进（需要 AT&T 语法）：
\n.global dividePower2\n dividePower2:\n sar $2, %esi\n ret\n是的，如果你想高效地做到这一点，算术右移是一个有用的部分。
但不，n >>= 2;这不是一件有用的事情。您所做的任何移位都需要是可变计数的（或者如果您要广播符号位以制作 0 / -1 掩码，则按 31 移位）。
n例如，看看编译器如何处理常量return x / (1<<11);。（神箭）。
# 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 >> n( sar %cl, %edi) 向 -Infinity 舍入，而不是向 0 截断。 x/2 和 x>>1 或 x*2 和 x << 1 之间的差异（其中 x 是整数）详细介绍了编译器如何实现 C 除法语义为了x/2或者x/8或者什么。
加法2047可以将小的负数包装成小的正数，但仅限于小于 1<<11 的数字。因此，后者sar会将所有设置的位移出并离开0，就像我们希望对幅度小于 2048 的原始小负数进行向零截断的除法一样。
对于较大数值的负数，添加一个正数会减小数值，从而减小商，除非它一开始就是精确倍数。（因为我们加了比除数少 1 的值）。这让我们可以使用sar（算术右移）向 -Infinity 舍入，考虑到它与我们想要的截断除法之间的小 1 差异。
对于变量计数 ，return x / (1<<n)编译器天真地只是具体化1<<n并使用idiv。但我们可以通过遵循与除以 2 的常数幂相同的模式来做得更好。
（n in 的范围限制[0,30]意味着1<<31溢出到INT_MIN不是问题。n=31不过，我认为该算法对于 可以正确工作。结果是0或-1，这是 32 位乘sar31 可能的两个结果。添加0x7fffffff到任何= 0x80000000之外的负数INT_MIN将产生一个非负数，因此sar产生 0。对于 x = INT_MIN，我们正在-1 >> 31给出-1。）
我们可以做x + (1<<n)-1并使用相同的 test/cmovns 让我们x或x + (1<<n)-1. 该-1部分可以作为 LEA 的一部分来完成。
1<<n进入 Intel CPU 的最有效方法是bts进入清零寄存器。（变量计数shl为 3 uops，除非我们使用 BMI2 sarx。并且0用 xor 实现 a 比 便宜mov $1, %eax。）在 AMD Zen 上，其中bts2 uops 但shl %cl, %eax只有 1 ( https://uops.info )，移动可能更便宜a1到 EAX 中shl，因为无论如何我们都需要 CL 中的移位计数以用于后面的sar. （除非我们有 BMI2，sarx它允许来自任何寄存器的班次计数。）
另一种选择是将BMI2(1<<n) - 1应用到；我认为这直接适用于包含范围（尽管仍然仅适用于 n=[0,31]）。它在 Intel 和 AMD 上是单微指令 ( https://uops.info/ )。见下文; 这就是 clang 对其 C 版本所做的事情。bzhi0xffffffffn[0,32]sar
# 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 个组件 ( ) 的 LEA[-1 + rax + rdi]在 Skylake 及更早版本上将具有 3 个周期延迟，但 Ice Lake 会以 1 个周期延迟运行。Ice Lake 及更高版本上的“慢速”LEA 无法在尽可能多的端口上运行，但不会产生延迟损失。（在 Alder Lake P 核上，缩放索引会像 Zen 系列一样花费 2 个周期延迟，即使它只是 2 组件 LEA，但我们不会在此处缩放索引。）在 Zen 系列上，此 3 组件 LEA 具有2 个周期延迟。Alder Lake E 核心也是如此。add因此，使用单独的指令进行操作并没有什么可以节省的dec。
另一种获取方式(1<<n) - 1是旧的 clang 所做的：0xffffffff >> (-n&31). 它实际上生成0xffffffff或广播符号位0。sar $31, reg但这种策略对于变量来说不太方便，n因为它需要否定。在没有 BMI2 的 x86 上尤其不方便，因为班次计数需要在 CL 中。
具有 SSE2 的 SIMD 版本pslld应该psrad是可能的，或者vpsllvd具有每个元素变量计数的 AVX2。
与 SSE4.1 混合pblendvps可以作为 scalar 的替代品cmov，但似乎更有效的东西应该是可能的。psrad也许使用get0或-1and 做一些事情会更麻烦？或者只是将其用作掩码，将非负元素中的向量pandn归零。结果可直接用作in 。1<<n - 1xpsrad-1(1<<n) - 1
// 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位模式和每个nfrom0到 的优化版本彻底测试参考版本31。它适用于所有情况。
当参考实现为 时return x / (1<<n)，它通过了 all n=0..30，但失败了-2147483648 / (1<<31) = 1（因为1<<31在参考实现中溢出到 INT_MIN，但位移版本给出了-1，因为它除以 2 的正幂。）我编译了gcc -O3 -fwrapv -march=native使有符号整数溢出定义明确，以便于测试 asm。
因此，这种优化不适用于x/(1<<n)with gcc -fwrapv，因为该n=31行为被明确定义为具有负除数。
但是，如果没有-fwrapv符号溢出是 C 中未定义行为的情况，则此优化将是有效的。TODO：向 GCC 和 clang 报告这个错过的优化。
对于 n=0..31 也有效x/(1LL<<n)，但对于 n=32 或更高版本无效，因为这在 C 中仍然定义良好。（我假设 x 是 32 位int，所以long long更宽；n=32..63有效并使商0.)
| 归档时间： |
|
| 查看次数： |
149 次 |
| 最近记录： |