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

Question

对于以下代码的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、依赖关系等)。

Answer 1

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，则分支版本应该可以很好地预测，并且非常好，因为分支预测 + 推测执行可以解耦数据依赖链。

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