换档操作后使用进位标志

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 中，因此在分支代码中，通过使用移位的 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 输出 for 而不是单独计算withcmovc的输入来保存 uop 。您仍然不会缩短关键路径，因为和可以并行运行，并且像 Haswell 或 Ryzen 这样的主流 CPU 拥有足够宽的管道来充分利用所有 ILP 以及循环承载依赖链上的瓶颈。（https://agner.org/optimize/）。cmovetesttestshrimul

实际上它是cmov-> imul-> 下一个迭代 dep 链，y这就是瓶颈。在 Haswell 及更早版本上，cmov延迟为 2 个周期（2 uops），因此总 dep 链为 2+3 = 5 个周期。（管道乘法器意味着进行额外的y*=1乘法不会减慢x*=x部件的速度，反之亦然；它们可以同时飞行，只是不在同一个周期中启动。）

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

否则，最好是承受无分支版本的较长延迟，而不是遭受分支错过。