时间戳

首页 > 解决方案 > 移位操作后使用进位标志

c++ - 移位操作后使用进位标志

问题描述

对于以下代码的 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 个寄存器和 and/test 代替）：https ://godbolt.org/z/L6VUZ1

所以我想知道如果你手工编码最好的方法是什么以及为什么（ILP，依赖项，......）。

标签： c++assemblyx86

解决方案

test/je可以宏融合到主流 Intel 和 AMD CPU 上的单个 uop 中，因此在分支代码中，通过使用 shift 的 CF 输出而不是早些时候test/je。

（不幸的是，gcc 在这里真的很愚蠢，并且使用test edx,edx的结果and edx,1，而不是仅仅使用test dl,1或更好test sil,1地保存mov。 test esi,1将使用 imm32 编码，因为没有test r/m32, imm8编码test，所以编译器知道读取窄寄存器test。）

但是在像 clang 这样使用的无分支实现中，是的，您可以通过使用 CF 输出来保存 uop，cmovc而不是单独计算cmovewith的输入test。您仍然不会缩短关键路径，因为test它shr可以并行运行，并且 Haswell 或 Ryzen 等主流 CPU 具有足够宽的管道来充分利用所有 ILP，并且只是imul循环承载依赖链上的瓶颈。（https://agner.org/optimize/）。

实际上它是cmov-> imul-> 下一次迭代 dep 链，因为y这是瓶颈。在 Haswell 及更早版本上，cmov延迟为 2 个周期（2 微秒），因此总的 dep 链为 2+3 = 5 个周期。（流水线乘法器意味着进行额外的y*=1乘法运算不会减慢x*=x零件的速度，反之亦然；它们可以同时运行，只是不在同一个循环中开始。）

如果您n对不同的基础重复使用相同的版本，则分支版本应该可以很好地预测，并且非常好，因为分支预测 + 推测执行可以解耦数据依赖链。

否则，最好吃掉无分支版本的较长延迟，而不是遭受分支未命中。

推荐阅读