相关: unsigned
饱和操作在纯 ISO C 中实现起来更加容易和高效: 如何在 C 中进行无符号饱和加法?
编译器对目前提出的所有纯C选项都不太擅长。它们没有意识到可以使用“add”指令的带符号溢出标志结果来检测饱和度是否达到INT64_MIN/MAX。据我所知,没有纯C模式被编译器识别为读取“add”的OF标志结果。在这里使用内联汇编并不是一个坏主意,但我们可以避免使用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的补码)这一事实,根据b
的符号选择INT64_MIN / MAX。通过使用uint64_t
进行加法运算来避免有符号整数溢出的未定义行为,并且GNU C定义了将无法表示其值的无符号整数转换为已知类型的行为(未更改使用的位模式)。当前gcc / clang受益于此指导,因为它们从三元运算符中不能理解这个技巧,例如(b<0) ? INT64_MIN : INT64_MAX
。(请参见下面使用该方法的备用版本)。我还没有检查过32位架构上的asm。
GCC仅支持二进制补码整数类型,因此使用__builtin_add_overflow
的函数不必考虑可移植性到使用一位补码(在那里相同的身份保持)或符号/幅度(在这种情况下不是)的C实现,即使您为long
或int
而不是int64_t
制作了一个版本。
#include <stdint.h>
#ifndef __cplusplus
#include <stdbool.h>
#endif
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) {
return ((uint64_t)b >> 63) + INT64_MAX;
}
return res;
}
另一个选项是
(b>>63) ^ INT64_MAX
,如果手动矢量化时SIMD XOR可以在比SIMD ADD更多的端口上运行,例如在Skylake之前的英特尔上可能会有用。 (但是x86没有SIMD 64位算术右移,只有逻辑右移,因此这只对
int32_t
版本有帮助,并且您需要有效地检测第一次溢出。或者您可以在符号位上使用可变混合,例如
blendvpd
)。请参见
Add saturate 32-bit signed ints intrinsics?与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,因为它必须在add之前准备饱和常量,保留两个操作数。
请注意,非溢出情况的关键路径仅包括一个add和一个未执行的jo。即使在Sandybridge系列上,它们也无法宏观融合成单个uop
甚至,但由于分支预测+推测执行,jo仅产生吞吐量而不是延迟。(在内联时,mov将消失。)
如果饱和度并不罕见且分支预测是一个问题,使用基于配置文件的优化编译,并且gcc会希望进行if转换并使用cmovno而不是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 太早,所以除了在宏中外无用。 (相关:ICC19 不通过
__builtin_saddll_overflow
进行常量传播:它将两个输入都放在寄存器中并仍然执行加法。GCC 和 Clang 只返回一个常量。)
在 hoisted MIN/MAX 选择的循环内部,此优化尤其有价值,只剩下 add
+ cmovo
。(或者 add
+ jo
到一个 mov
。)
cmov
是英特尔P6家族和SnB家族在Broadwell之前的一条2微操作指令,因为它有3个输入。在其他x86 CPU(Broadwell / Skylake 和 AMD)上,它是一个单微操作指令。在大多数这样的CPU上,它具有1个周期的延迟。它是一个简单的ALU选择操作;唯一的复杂性是3个输入(2个寄存器+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 或其他类似指令进行选择。
我们可以假设使用的是二进制补码,因为 gcc 仅支持二进制补码整数类型,而 ISO C 可选的 int64_t
类型如果存在,则保证为二进制补码。(int64_t
的有符号溢出仍然是未定义行为,这允许它成为 long
或 long long
的简单 typedef
。)
在支持某种等效于
__builtin_add_overflow
的符号/幅值C实现中,一个针对
long long
或
int
的函数版本不能使用SHR / ADD技巧。为了极大的可移植性,你可能只需使用简单的三元运算符,或者特别针对符号/幅值,你可以
return (b&0x800...) | 0x7FFF...
将
b
的符号位与最大幅值数进行按位或操作。
对于二进制补码,MIN和MAX的位模式分别为0x8000...
(只有高位设置)和0x7FFF...
(所有其他位设置)。它们具有一些有趣的属性:MIN = MAX + 1
(如果使用无符号计算),MIN = ~MAX
:它们的位模式是按位反转,也就是互为一的补码。
MIN = ~MAX
属性是从~x = -x - 1
(标准的-x = ~x + 1
2's complement identity的重新排列)和MIN = -MAX - 1
这个事实得出的。而+1
属性与此无关,它只是从最正到最负的简单翻转中产生,并适用于有符号整数的补码编码。(但不适用于符号/大小;在无符号大小中会得到-0
)。
上述函数使用了“MIN = MAX + 1”技巧。通过算术右移(创建“0”或“0xFF…”)将符号位广播到所有位置,并与之异或,也可以使用“MIN = ~MAX”技巧。GNU C保证有符号右移是算术(符号扩展),因此在GNU C中,“(b>>63) ^ INT64_MAX”等同于“(b<0) ? INT64_MIN : INT64_MAX”。
ISO C使有符号右移的实现是定义的,但我们可以使用“b<0 ? ~0ULL : 0ULL”的三元运算符。编译器将优化以下内容以进行sar / xor或等效指令,但它没有实现定义的行为。AArch64可以像使用add一样使用移位输入操作数来使用eor。
// 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”指令:条件选择反转。由于其强大的立即编码,可以使用单个32位“mov”指令将INT64_MIN放入寄存器,以获得简单的位模式。 AArch64 GCC已经使用了“csinv”进行原始“return(b <0)?INT64_MIN:INT64_MAX;”版本的“MIN =〜MAX”技巧。
clang 6.0及更早版本在Godbolt上使用shr / add进行普通的“(b <0)?INT64_MIN:INT64_MAX;”版本。它看起来比clang7/8更有效,因此我认为这是一种回归/错过优化错误。 (这就是本节的全部内容以及我写第二版的原因。)
我选择了
MIN = MAX + 1
版本,因为它有可能更好地自动矢量化:x86 拥有 64 位 SIMD 逻辑右移,但只有 16 位和 32 位 SIMD 算术右移
直到 AVX512F。当然,对于 64 位整数,使用 SIMD 进行有符号溢出检测可能不值得,直到 AVX512。好吧,也许是 AVX2。如果它是一些可以以其他方式高效矢量化的更大计算的一部分,那么解包到标量再返回就很糟糕。
对于标量来说,这真的没有区别;无论哪种方式编译效果都相同,sar/shr
的表现也相同,在 Agner Fog 测试过的所有 CPU 上都是如此https://agner.org/optimize/。
但是,
+
有时候会被优化成其他东西,所以你可以想象gcc将常量后面的
+
或
-
折叠到溢出分支中。或者可能使用
LEA
来复制并添加而不是
ADD
。从一个更简单的ALU执行单元执行XOR与ADD之间的功率差异将在超出顺序执行和其他操作所需的所有功率的噪声中丢失;即使对于64位整数,即使在P4 Prescott / Nocona上,所有x86 CPU都具有单周期标量ADD和XOR,其具有异乎寻常的加法器。
此外,@chqrlie建议以紧凑易读的方式编写它,而不需要UB,看起来比超级可移植的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) {
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的内联汇编所做的事情,但用一个
test
替换了一个cmov。(当然,cmov上的条件不同。)
与使用shr/add的
_v2
相比,这种方法的另一个缺点是需要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,然后再次对
saddll_overflow
结果使用
test
将其放回FLAGS中。重新排列源代码解决了这个问题。
(x < 0)
呢?为了可移植性,请使用[u]int64_t
。这样你就可以免费使用INT64_MAX
和INT64_MIN
,而不必使用自己的常量来实现。 - Jens Gustedtx+1 > x
编译成常数1
)。仅因为这个原因,我认为这个问题不应该被关闭,因为所引用的答案都没有考虑到这一点...... - Nemo