对于以下代码的div/mod部分:
int pow(int x, unsigned int n)
{
int y = 1;
while (n > 1)
{
auto m = n%2;
n = n/2;
if (m)
y *= x;
x = x*x;
}
return x*y;
}
我希望像这样组装
shr n
cmovc y, yx
但是 gcc/clang 甚至 icc 在这里都不使用进位标志(而是使用 2 个寄存器和/测试):https://godbolt.org/z/L6VUZ1
所以我想知道如果您手动编码最好的方法是什么以及为什么(ILP、依赖关系等)。
最佳答案
test/je
可以在主流 Intel 和 AMD CPU 上宏融合为单个 uop,因此在分支代码中,您只会节省代码大小并花费 1 个分支未命中周期-通过使用移位的 CF 输出而不是早期的 test/je
来检测延迟。
(不幸的是,gcc 在这里真的很笨,它在 和 edx,1
的结果上使用了 test edx,edx
,而不是仅仅使用 test dl,1
或更好的 test sil,1
来保存 mov
。test esi,1
将使用 imm32 编码,因为有没有 test r/m32, imm8
编码用于 test
,因此编译器知道读取窄寄存器用于 test
。)
但是在像 clang 使用的无分支实现中,是的,您可以通过使用 cmovc
的 CF 输出来保存一个 uop,而不是使用 cmove
单独计算输入 测试
。你仍然没有缩短关键路径,因为 test
和 shr
可以并行运行,并且像 Haswell 或 Ryzen 这样的主流 CPU 有足够宽的管道来充分利用所有 ILP 和只是 imul
循环携带的依赖链上的瓶颈。 (https://agner.org/optimize/)。
实际上,cmov
-> imul
-> y
的下一次迭代 dep 链是瓶颈。在 Haswell 和更早版本上,cmov
是 2 个周期的延迟(2 微秒),所以总的 dep 链是 2+3 = 5 个周期。 (流水线乘法器意味着执行额外的 y*=1
乘法不会减慢 x*=x
部分的速度,反之亦然;它们可以同时运行只是不在同一个周期中开始。)
如果您对不同的基础重复使用相同的 n
,则分支版本应该可以很好地预测,并且非常好,因为分支预测 + 推测执行可以解耦数据依赖链。
否则最好吃无分支版本的较长延迟,而不是遭受分支未命中。
关于c++ - 移位操作后使用进位标志,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52873488/