drw*_*owe 11 c optimization x86-64 addition saturation-arithmetic
我正在寻找一些用于签名饱和64位加法的C代码,它使用gcc优化器编译为高效的X86-64代码.便携式代码是理想的,尽管如果需要可以使用asm解决方案.
static const int64 kint64max = 0x7fffffffffffffffll;
static const int64 kint64min = 0x8000000000000000ll;
int64 signed_saturated_add(int64 x, int64 y) {
bool x_is_negative = (x & kint64min) != 0;
bool y_is_negative = (y & kint64min) != 0;
int64 sum = x+y;
bool sum_is_negative = (sum & kint64min) != 0;
if (x_is_negative != y_is_negative) return sum; // can't overflow
if (x_is_negative && !sum_is_negative) return kint64min;
if (!x_is_negative && sum_is_negative) return kint64max;
return sum;
}
写入的函数产生具有多个分支的相当长的汇编输出.有关优化的提示吗？看起来它应该只用一个带有一些CMOV指令的ADD来实现,但我对这些东西有点生疏.
oua*_*uah 10
这可能会进一步优化,但这是一个便携式解决方案.它不会调用未定义的行为,它会在可能发生之前检查整数溢出.
#include <stdint.h>
int64_t sadd64(int64_t a, int64_t b)
{
if (a > 0) {
if (b > INT64_MAX - a) {
return INT64_MAX;
}
} else if (b < INT64_MIN - a) {
return INT64_MIN;
}
return a + b;
}
这是一种解决方案，该解决方案延续了其中一项评论中给出的内容，并且也已用于ouah的解决方案中。这里生成的代码应该没有条件跳转
int64_t signed_saturated_add(int64_t x, int64_t y) {
// determine the lower or upper bound of the result
int64_t ret = (x < 0) ? INT64_MIN : INT64_MAX;
// this is always well defined:
// if x < 0 this adds a positive value to INT64_MIN
// if x > 0 this subtracts a positive value from INT64_MAX
int64_t comp = ret - x;
// the condition is equivalent to
// ((x < 0) && (y > comp)) || ((x >=0) && (y <= comp))
if ((x < 0) == (y > comp)) ret = x + y;
return ret;
}
第一个看起来好像有条件要执行，但是由于特殊的值，我的编译器加上了一个附加值：2的补码INT64_MIN是INT64_MAX+1。如果没有问题，那么只有一个条件移动可以分配和。
所有这些都没有UB，因为在抽象状态机中，总和仅在没有溢出的情况下完成。
相关：unsigned饱和更容易，并且在纯 ISO C 中有效地可能：如何在 C 中进行无符号饱和加法？
编译器在迄今为止提出的所有纯 C 选项中都很糟糕。
他们没有看到他们可以使用add指令的有符号溢出标志结果来检测到 INT64_MIN/MAX 的饱和是必要的。AFAIK 没有纯 C 模式被编译器识别为读取add.
内联汇编在这里并不是一个坏主意，但是我们可以通过 GCC 的内置函数来避免这种情况，这些内置函数将 UB 安全包装签名加法与布尔溢出结果公开。 https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html
（如果您打算使用 GNU C 内联汇编，那将限制您与这些 GNU C 内置函数一样多。而且这些内置函数不是特定于架构的。它们确实需要 gcc5 或更新版本，但 gcc4.9 和更早版本基本上是过时了 。https ://gcc.gnu.org/wiki/DontUseInlineAsm - 它阻碍了持续传播并且难以维护。）
这个版本使用的事实是INT64_MIN = INT64_MAX + 1ULL（对于 2 的补码）根据 的符号选择 INT64_MIN/MAX b。有符号溢出 UB 通过使用uint64_tfor 来避免，并且 GNU C 定义了将无符号整数转换为不能表示其值的有符号类型的行为（使用的位模式不变）。当前的 gcc/clang 受益于这种牵手，因为他们没有从像(b<0) ? INT64_MIN : INT64_MAX. （有关使用它的替代版本，请参见下文）。我还没有检查 32 位架构上的 asm。
GCC 仅支持 2 的补码整数类型，因此使用的函数__builtin_add_overflow不必关心使用 1 的补码（相同身份的情况）或符号/幅度（不存在的情况）的C 实现的可移植性，即使您做了用于long或int代替int64_t.
#include <stdint.h>
#ifndef __cplusplus
#include <stdbool.h>
#endif
// static inline
int64_t signed_sat_add64_gnuc_v2(int64_t a, int64_t b) {
long long res;
bool overflow = __builtin_saddll_overflow(a, b, &res);
if (overflow) {
// overflow is only possible in one direction depending on the sign bit
return ((uint64_t)b >> 63) + INT64_MAX;
// INT64_MIN = INT64_MAX + 1 wraparound, done with unsigned
}
return res;
}
(b>>63) ^ INT64_MAX如果手动矢量化 SIMD XOR 可以在比 SIMD ADD 多的端口上运行的位置（例如在 Skylake 之前的 Intel 上），则另一个选项可能很有用。（但 x86 没有 SIMD 64 位算术右移，只有逻辑，所以这只会对一个int32_t版本有帮助，你首先需要有效地检测溢出。或者你可以在符号位，如blendvpd）参见添加饱和 32 位有符号整数内在函数？使用 x86 SIMD 内在函数 (SSE2/SSE4)
在带有 gcc9 和 clang8 的 Godbolt 上（以及来自其他答案的其他实现）：
# gcc9.1 -O3 (clang chooses branchless with cmov)
signed_sat_add64_gnuc_v2:
add rdi, rsi # the actual add
jo .L3 # jump on signed overflow
mov rax, rdi # retval = the non-overflowing add result
ret
.L3:
movabs rax, 9223372036854775807 # INT64_MAX
shr rsi, 63 # b is still available after the ADD
add rax, rsi
ret
内联到循环中时，mov imm64可以提升。如果b之后需要，那么我们可能需要一个额外的mov，否则shr/add可能会破坏b，使INT64_MAX寄存器中的常量完好无损。或者，如果编译器想要使用cmov（就像 clang 一样），它必须mov/shr因为它必须在添加之前准备好饱和常数，同时保留两个操作数。
请注意，非溢出情况的关键路径仅包括 anadd和 not-takenjo。即使在 Sandybridge-family 上，这些也不能宏融合到单个uop 中，但jo由于分支预测 + 推测执行，唯一的成本是吞吐量而不是延迟。（内联时，mov将消失。）
如果饱和实际上并不罕见并且分支预测是一个问题，则使用配置文件引导优化进行编译， gcc 有望进行 if 转换并使用 acmovno而不是jo，就像 clang 所做的那样。这会将 MIN/MAX 选择以及 CMOV 本身置于关键路径上。MIN/MAX 选择可以与add.
你可以用a<0。我使用b是因为我认为大多数人会写x = sadd(x, 123)而不是x = sadd(123, x)，并且有一个编译时常量可以b<0优化掉. 为了获得最大的优化机会，您可以使用if (__builtin_constant_p(a))询问编译器是否a为编译时常量。这适用于 gcc，但是在内联之前，clang 过早地评估了 const-ness 方式，因此除了在带有 clang 的宏中之外，它没有用。（相关：ICC19 不通过常量传播__builtin_saddll_overflow：它将两个输入都放入寄存器并仍然进行加法。GCC和 Clang 只返回一个常量。）
这种优化在 MIN/MAX 选择提升的循环内特别有价值，只留下add+ cmovo。（或add+jo到一个mov。）
cmov是 Broadwell 之前的 Intel P6 系列和 SnB 系列的 2 uop 指令，因为它有 3 个输入。在其他 x86 CPU（Broadwell / Skylake 和 AMD）上，它是单 uop 指令。在大多数此类 CPU 上，它具有 1 个周期的延迟。这是一个简单的 ALU 选择操作；的唯一的并发症是3个输入（2个REG + FLAGS）。但是在 KNL 上它仍然是 2 周期延迟。
不幸的是，AArch64 的 gcc 无法用于adds设置标志并检查 V（溢出）标志结果，因此它花费了几条指令来决定是否进行分支。
Clang 做得很好，AArch64 的立即编码可以表示INT64_MAX为eor或的操作数add。
// clang8.0 -O3 -target aarch64
signed_sat_add64_gnuc:
orr x9, xzr, #0x7fffffffffffffff // mov constant = OR with zero reg
adds x8, x0, x1 // add and set flags
add x9, x9, x1, lsr #63 // sat = (b shr 63) + MAX
csel x0, x9, x8, vs // conditional-select, condition = VS = oVerflow flag Set
ret
MIN与MAX选择如上所述，return (b<0) ? INT64_MIN : INT64_MAX;大多数版本的 gcc/clang 不能以最佳方式编译；它们在寄存器和 cmov 中生成常量以进行选择，或者在其他 ISA 上生成类似的东西。
我们可以假设 2 的补码，因为GCC 只支持 2 的补码整数类型，并且因为 ISO C 可选int64_t类型保证是 2 的补码（如果存在）。（签名溢出int64_t仍然是 UB，这使它成为一个简单typedef的longor long long）。
（在支持某些等价物的符号/幅度 C 实现上，__builtin_add_overflow此函数的一个版本用于long long或int不能使用 SHR / ADD 技巧。对于极端的可移植性，您可能只使用简单的三元，或专门用于符号/幅度您可以return (b&0x800...) | 0x7FFF...将 的符号位 ORb转换为最大数量。）
对于二进制补码，MIN 和 MAX 的位模式是0x8000...（仅设置高位）和0x7FFF...（设置所有其他位）。它们有几个有趣的属性：（MIN = MAX + 1如果在位模式上使用无符号计算），并且MIN = ~MAX：它们的位模式是按位逆，也就是彼此的补码。
该MIN = ~MAX性质来自~x = -x - 1（标准-x = ~x + 1 2 的补码身份的重新排列）以及MIN = -MAX - 1. 该+1属性是不相关的，并且遵循从最正到最负的简单翻转，并且也适用于有符号整数的补码编码。（但不是符号/幅度；你会得到-0无符号幅度的位置）。
上面的函数使用了这个MIN = MAX + 1技巧。 该MIN = ~MAX技巧也可以通过使用算术右移（创建0或0xFF...）将符号位广播到所有位置并与之异或来使用。GNU C 保证有符号右移是算术（符号扩展），所以在 GNU C 中(b>>63) ^ INT64_MAX是等价的(b<0) ? INT64_MIN : INT64_MAX。
ISO C 留下了实现定义的带符号右移，但我们可以使用b<0 ? ~0ULL : 0ULL. 编译器会将以下优化为sar/xor或等效指令，但它没有实现定义的行为。AArch64 可以eor像add.
// an earlier version of this answer used this
int64_t mask = (b<0) ? ~0ULL : 0; // compiles to sar with good compilers, but is not implementation-defined.
return mask ^ INT64_MAX;
有趣的事实：AArch64 有一条csinv指令：conditional-select inverse。它可以将 INT64_MIN 放入带有单个 32 位mov指令的寄存器中，这要归功于其对简单位模式的强大立即编码。AArch64 GCC 已经用于原始版本csinv的MIN = ~MAX技巧return (b<0) ? INT64_MIN : INT64_MAX;。
在 Godbolt 上，clang 6.0 及更早版本使用shr/add作为普通(b<0) ? INT64_MIN : INT64_MAX;版本。它看起来比 clang7/8 更有效，所以我认为这是一个回归/遗漏优化错误。（这是本节的重点，也是我写第二个版本的原因。）
我选择这个MIN = MAX + 1版本是因为它可以更好地自动矢量化：x86 具有 64 位 SIMD 逻辑右移，但只有 16 位和 32 位 SIMD 算术右移，直到 AVX512F。 当然，在 64 位整数的 AVX512 之前，使用 SIMD 进行有符号溢出检测可能不值得。好吧，也许是 AVX2。如果它是一些较大计算的一部分，否则可以有效地进行矢量化，那么解包为标量并返回很糟糕。
对于标量，它确实是一种清洗；两种方法都不能编译更好，并且在 Agner Fog 测试过的所有 CPU 上sar/shr执行相同，也是如此add/xor。（https://agner.org/optimize/）。
但是+有时可以优化为其他东西，因此您可以想象 gcc 将稍后+或-常量折叠到溢出分支中。或者可能LEA用于添加而不是ADD复制和添加。用于 XOR 和 ADD 的更简单 ALU 执行单元的功率差异将在噪声中消失，因为它会消耗所有功率来进行乱序执行和其他事情；所有 x86 CPU 都具有单周期标量 ADD 和 XOR，即使对于 64 位整数，即使在具有奇特加法器的 P4 Prescott/Nocona 上也是如此。
@chqrlie 还建议了一种紧凑的可读方式，在没有 UB 的情况下用 C 编写它，这看起来比超级便携的int mask = ternary东西更好。
不依赖于 MIN/MAX 的任何特殊属性，因此对于具有其他溢出检测条件的其他边界可能很有用。或者如果编译器在这个版本上做得更好。
int64_t signed_sat_add64_gnuc(int64_t a, int64_t b) {
long long res;
bool overflow = __builtin_saddll_overflow(a, b, &res);
if (overflow) {
// overflow is only possible in one direction for a given `b`
return (b<0) ? INT64_MIN : INT64_MAX;
}
return res;
}
编译如下
# gcc9.1 -O3 (clang chooses branchless)
signed_sat_add64_gnuc:
add rdi, rsi # the actual add
jo .L3 # jump on signed overflow
mov rax, rdi # retval = the non-overflowing add result
ret
.L3:
movabs rdx, 9223372036854775807
test rsi, rsi # one of the addends is still available after
movabs rax, -9223372036854775808 # missed optimization: lea rdx, [rax+1]
cmovns rax, rdx # branchless selection of which saturation limit
ret
这基本上是@drwowe 的内联asm 所做的，但test替换了一个cmov。（当然还有 cmov 上的不同条件。）
与_v2with shr/add相比，此方法的另一个缺点是它需要 2 个常量。在循环中，这会占用一个额外的寄存器。（同样，除非b是编译时常量。）
clang 使用cmov而不是分支，并且确实发现了lea rax, [rcx + 1]避免第二个 10 字节mov r64, imm64指令的技巧。（或 clang6.0 及更早版本使用shr 63/add技巧而不是 cmov。）
这个答案的第一个版本放在int64_t sat = (b<0) ? MIN : MAX之外if()，但是 gcc 错过了在分支内移动它的优化，因此它根本不会在非溢出情况下运行。这甚至比在关键路径之外运行它还要好。（如果编译器决定无分支也没关系）。
但是，当我把它放在外面的if和之后的__builtin_saddll_overflow，GCC是非常愚蠢的，并保存在bool一个整数结果，然后做测试/ CMOV，然后使用test上saddll_overflow再次结果放回标志。重新排序源解决了这个问题。
我仍在寻找一个像样的便携式解决方案，但这已经是我迄今为止想到的最好的解决方案了：
改进建议？
int64 saturated_add(int64 x, int64 y) {
#if __GNUC__ && __X86_64__
asm("add %1, %0\n\t"
"jno 1f\n\t"
"cmovge %3, %0\n\t"
"cmovl %2, %0\n"
"1:" : "+r"(x) : "r"(y), "r"(kint64min), "r"(kint64max));
return x;
#else
return portable_saturated_add(x, y);
#endif
}
| 归档时间： |
|
| 查看次数： |
1919 次 |
| 最近记录： |