关于ADC，-1（0xFFFFFFFF）有什么特别之处吗？

Question

在我的一个研究项目中，我正在编写 C++ 代码。但是，生成的程序集是该项目的关键点之一。 C++ 不提供对标志操作指令的直接访问，特别是对 ADC 的直接访问，但这应该不是问题，前提是编译器足够聪明，可以使用它。考虑：

constexpr unsigned X = 0;

unsigned f1(unsigned a, unsigned b) {
    b += a;
    unsigned c = b < a;
    return c + b + X;
}

变量 c 是一种解决方法，可以让我掌握进位标志并将其添加到 b 和 X。看起来我很幸运，（g++ -O3，版本 9.1）生成的代码是这样的：

f1(unsigned int, unsigned int):
 add %edi,%esi
 mov %esi,%eax
 adc [=11=]x0,%eax
 retq

对于我测试过的所有 X 值，代码都如上（当然除了立即值 [=22=]x0 会相应更改）。不过，我发现了一个例外：当 X == -1（或 0xFFFFFFFFu 或 ~0u，...如何拼写并不重要）生成的代码是：

f1(unsigned int, unsigned int):
 xor %eax,%eax
 add %edi,%esi
 setb %al
 lea -0x1(%rsi,%rax,1),%eax
 retq

这似乎比间接测量建议的初始代码效率低（虽然不是很科学）我说得对吗？如果是这样，这是"missing optimization opportunity" 那种值得报告的错误？

值得一提的是，clang -O3，版本 8.8.0，总是使用 ADC（如我所愿），而 icc -O3，版本 19.0.1 从不使用。

我试过使用内在函数 _addcarry_u32 但没有用。

unsigned f2(unsigned a, unsigned b) {
    b += a;
    unsigned char c = b < a;
    _addcarry_u32(c, b, X, &b);
    return b;
}

我想我可能没有正确使用 _addcarry_u32（我找不到太多关于它的信息）。既然由我来提供进位标志，那么使用它有什么意义呢？（再次，引入c，祈祷编译器了解情况。）

实际上，我可能会正确使用它。对于 X == 0 我很高兴：

f2(unsigned int, unsigned int):
 add %esi,%edi
 mov %edi,%eax
 adc [=14=]x0,%eax
 retq

对于X == -1我不开心:-(

f2(unsigned int, unsigned int):
 add %esi,%edi
 mov [=15=]xffffffff,%eax
 setb %dl
 add [=15=]xff,%dl
 adc %edi,%eax
 retq

我确实得到了 ADC 但这显然不是最有效的代码。（dl 在那里做什么？两条指令读取进位标志并恢复它？真的吗？我希望我错了！）

Answer 1

mov + adc $-1, %eax 比 xor-zero + setc + 3-component lea 更有效和 uop 在大多数 CPU 上计数，在任何 still-relevant CPU 上都不差。¹

这看起来像是 gcc 错过了优化：它可能看到了一个特殊情况并抓住了它，搬起石头砸自己的脚并阻止 adc 模式识别正在发生。

我不知道它到底看到了什么/在寻找什么，所以是的，您应该将此报告为 missed-optimization 错误。或者，如果您想自己深入挖掘，可以在优化通过后查看 GIMPLE 或 RTL 输出，看看会发生什么。如果您对 GCC 的内部表示有所了解。 Godbolt 有一个 GIMPLE tree-dump window，您可以从与 "clone compiler".

相同的下拉列表中添加

clang 用 adc 编译它的事实证明它是合法的，即你想要的 asm 确实匹配 C++ 源，你没有错过一些阻止编译器这样做的特殊情况优化。（假设clang是bug-free，这里就是这样。）

如果你不小心，这个问题肯定会发生，例如尝试编写一个 general-case adc 函数，它接受进位并从 3 输入加法提供 carry-out 在 C 中很难，因为两个加法中的任何一个都可以进位，所以你不能在将进位添加到其中一个输入后，只需使用 sum < a+b 习惯用法。我不确定是否有可能让 gcc 或 clang 发出 add/adc/adc 其中中间 adc 必须采用 carry-in 并产生 carry-out.

例如0xff...ff + 1 回绕到 0，因此 sum = a+b+carry_in / carry_out = sum < a 无法优化为 adc 因为它需要 ignore 进位a = -1 和 carry_in = 1.

的特殊情况

所以另一个猜测是，也许 gcc 考虑过更早地执行 + X，并且因为那个特殊情况而搬起石头砸自己的脚。不过，这并没有多大意义。

What's the point of using it since it's up to me to provide the carry flag?

您使用 _addcarry_u32 正确。

它存在的意义在于让你表达一个带进位in和进位out的加法，这是hard in pure C. GCC 和 clang 没有优化好，经常不只是把进位结果保存在 CF 中。

如果你只想要carry-out，你可以提供一个0作为进位，它会优化为add而不是adc，但仍然给你carry-out 作为 C 变量。

例如在 32 位块中添加两个 128 位整数，你可以这样做

// bad on x86-64 because it doesn't optimize the same as 2x _addcary_u64
// even though __restrict guarantees non-overlap.
void adc_128bit(unsigned *__restrict dst, const unsigned *__restrict src)
{
    unsigned char carry;
    carry = _addcarry_u32(0, dst[0], src[0], &dst[0]);
    carry = _addcarry_u32(carry, dst[1], src[1], &dst[1]);
    carry = _addcarry_u32(carry, dst[2], src[2], &dst[2]);
    carry = _addcarry_u32(carry, dst[3], src[3], &dst[3]);
}

(On Godbolt with GCC/clang/ICC)

与编译器只使用 64 位 add/adc 的 unsigned __int128 相比，这是非常低效的，但确实会让 clang 和 ICC 发出一串 add/adc/adc/adc。 GCC 弄得一团糟，使用 setcc 将 CF 存储为某些步骤的整数，然后 add dl, -1 将其放回 CF 以获得 adc.

不幸的是，GCC 在用纯 C 编写的 extended-precision / biginteger 方面很糟糕。Clang 有时会稍微好一点，但大多数编译器都不擅长。这就是为什么大多数架构的 lowest-level gmplib 函数在 asm 中是 hand-written。

脚注 1：或微指令计数：在 Intel Haswell 和更早版本上等于 adc 是 2 微指令，但立即数为零除外 Sandybridge-family的解码器特例为 1 uop.

但是带有 base + index + disp 的 3 分量 LEA 使其成为 Intel CPU 上的 3 周期延迟指令，所以它肯定更糟。

在 Intel Broadwell 及更高版本上，adc 是一个 1-uop 指令，即使是 non-zero 立即数，利用 Haswell 为 FMA 引入的对 3-input uops 的支持。

如此相等的总 uop 计数但更差的延迟意味着 adc 仍然是更好的选择。

https://agner.org/optimize/

关于ADC，-1（0xFFFFFFFF）有什么特别之处吗？

Is there anything special about -1 (0xFFFFFFFF) regarding ADC?

c++

x86

assembly

gcc

bigint